수족관의 두 가지 장식

문제

한 수족관은 새 전시 수조에 놓을 장식을 고르고 있다. 사용할 수 있는 장식은 산호 모양 장식과 바위 모양 장식의 두 종류다. 같은 종류의 장식은 가격과 전시 점수가 모두 같다. 전시 점수는 장식을 놓았을 때 수조의 꾸밈 효과를 나타내는 정수이며, 여러 장식을 놓으면 각 장식의 점수를 단순히 더한 값이 전체 전시 점수가 된다. 담당자는 정해진 예산 안에서 전체 전시 점수가 가장 높아지도록 장식을 구매하려 한다. 산호 장식은 최대 A개, 바위 장식은 최대 C개까지 놓을 수 있다. 이 제한은 종류별 설치 공간 때문에 생긴 것이므로 두 종류의 개수 제한을 각각 지켜야 한다. 한 종류를 전혀 구매하지 않아도 되며, 두 종류 모두 구매하지 않는 선택도 가능하다. 장식은 정수 개만 구매할 수 있고, 일부를 잘라 구매하거나 구매한 장식을 되파는 것은 허용하지 않는다. 산호 장식 한 개의 가격은 P이고 전시 점수는 U다. 바위 장식 한 개의 가격은 Q이고 전시 점수는 V다. 산호를 x개, 바위를 y개 구매하면 비용은 P×x+Q×y이고 전시 점수는 U×x+V×y다. 비용이 예산 B와 정확히 같은 선택도 허용한다. 예산을 모두 사용할 필요는 없으며, 남은 예산은 전시 점수에 영향을 주지 않는다. 조건을 만족하는 선택 중 전시 점수가 가장 높은 선택을 구하는 프로그램을 작성하라. 최고 점수를 얻는 선택이 여러 개라면 구매하는 장식의 총개수가 가장 작은 선택을 고른다. 총개수도 같다면 산호 장식의 개수가 가장 작은 선택을 고른다. 이 규칙을 적용하면 선택은 하나로 정해진다. 어떤 장식도 구매할 수 없다면 산호와 바위의 구매 개수 및 전시 점수를 모두 0으로 출력한다. 두 종류의 가격과 점수가 서로 같을 수도 있다.

입력

첫째 줄에 정수 예산 B가 주어진다. 0 ≤ B ≤ 100,000이다.
둘째 줄에 산호 장식의 가격 P, 전시 점수 U, 최대 개수 A가 공백으로 주어진다.
셋째 줄에 바위 장식의 가격 Q, 전시 점수 V, 최대 개수 C가 공백으로 주어진다.
1 ≤ P, Q, U, V ≤ 1,000이며, 0 ≤ A, C ≤ 200이다. 입력의 모든 수는 정수다.

출력

선택한 산호 장식의 개수, 바위 장식의 개수, 전체 전시 점수를 공백으로 구분하여 한 줄에 출력한다.

10
3 4 3
4 5 2

2 1 13

1
2 5 4
3 7 2

0 0 0

4
2 3 2
2 3 2

0 2 6

출처: Devin.KR 자체 제작