창구의 두 가지 동전 묶음

문제

은행 창구에서는 고객에게 줄 동전을 미리 봉인한 묶음으로 준비한다. 오늘 사용할 수 있는 묶음은 두 종류이며, 첫 번째 묶음에는 A원, 두 번째 묶음에는 B원이 들어 있다. 두 종류의 묶음은 창구에 충분히 많이 준비되어 있어 재고는 고려하지 않는다. 다만 봉인을 풀어 일부 동전만 꺼내거나 서로 다른 묶음을 합쳐 새 묶음을 만드는 일은 허용하지 않는다. 한 고객은 최대 M원까지 동전으로 받으려 한다. 창구의 운반 상자에는 종류에 관계없이 묶음을 합하여 최대 K개까지 넣을 수 있다. 담당자는 첫 번째 묶음을 x개, 두 번째 묶음을 y개 선택한다. x와 y는 각각 0 이상의 정수여야 하고, 선택한 전체 묶음 수 x+y는 K 이하여야 한다. 또한 지급액 A×x+B×y는 고객이 정한 M원을 넘을 수 없다. 고객은 한도 안에서 가능한 한 많은 금액을 받기를 원한다. 따라서 먼저 지급액이 가장 큰 선택을 찾는다. 같은 최대 지급액을 만드는 선택이 여러 개라면 운반을 쉽게 하기 위해 전체 묶음 수가 가장 적은 선택을 고른다. 지급액과 전체 묶음 수까지 같다면 첫 번째 묶음의 개수 x가 가장 작은 선택을 고른다. 이 규칙을 순서대로 적용하면 출력할 x와 y는 하나로 결정된다. 두 묶음의 금액 A와 B가 같을 수도 있으며, 금액의 크기와 종류의 번호 사이에는 정해진 관계가 없다. 어느 종류도 반드시 사용할 필요는 없다. 한 개의 묶음도 한도 안에 들어가지 않거나 상자에 묶음을 넣을 수 없으면 x=0, y=0을 선택한다. 아무것도 선택하지 않는 경우의 지급액은 0원이고 전체 묶음 수도 0개다. 입력으로 주어진 금액과 상자 용량에 대해 규칙에 맞는 최대 지급액과 두 종류의 묶음 개수를 구한다.

입력

첫째 줄에 정수 A, B, M, K가 공백으로 구분되어 주어진다. 1≤A,B≤1,000,000, 0≤M≤1,000,000,000, 0≤K≤100,000이다. 모든 금액의 단위는 원이다.

출력

최대 지급액, 첫 번째 묶음의 개수 x, 두 번째 묶음의 개수 y를 공백으로 구분하여 한 줄에 출력한다. 지급액이 같으면 전체 묶음 수가 가장 적어야 하며, 그것도 같으면 x가 가장 작아야 한다. 아무 묶음도 선택할 수 없으면 0 0 0을 출력한다.

7 11 30 4

29 1 2

5 5 20 3

15 0 3

8 13 7 10

0 0 0

출처: Devin.KR 자체 제작