은행 창구의 봉인 묶음

문제

은행 창구에서는 행사장에 보낼 현금을 미리 봉인한 묶음으로 준비한다. 사용할 수 있는 묶음은 가형과 나형 두 종류다. 가형 묶음 하나에는 A원, 나형 묶음 하나에는 B원이 들어 있다. 두 종류는 포장 방식이 서로 다르므로, 들어 있는 금액이 같더라도 다른 종류로 취급한다. 각 종류의 묶음은 필요한 만큼 충분히 준비되어 있다. 담당 직원은 정확히 T원을 상자 하나에 담으려고 한다. 봉인을 뜯어 일부 금액만 꺼내거나, 묶음 이외의 현금을 추가할 수는 없다. 따라서 가형 묶음을 x개, 나형 묶음을 y개 담는다면 두 금액의 합이 정확히 T원이어야 한다. x와 y는 모두 0 이상의 정수이며, 한 종류의 묶음을 전혀 사용하지 않는 것도 허용한다. 보낼 금액이 0원이라면 아무 묶음도 담지 않는 방법을 사용할 수 있다. 운반 상자에는 금액과 관계없이 묶음을 최대 K개까지 담을 수 있다. 가형과 나형의 개수를 합한 값이 K를 넘는 구성은 금액이 맞더라도 사용할 수 없다. 묶음의 배치 순서는 구별하지 않는다. 예를 들어 같은 종류별 개수를 갖는 두 배치는 하나의 구성으로 취급한다. 상자의 무게나 묶음별 크기에 관한 추가 조건은 없다. 사용할 수 있는 구성이 여러 개라면 직원은 봉인 확인 작업을 줄이기 위해 전체 묶음 수가 가장 적은 구성을 선택한다. 전체 묶음 수까지 같다면 가형 묶음의 개수가 더 적은 구성을 선택한다. 이 기준을 차례로 적용하면 출력해야 할 종류별 개수가 하나로 정해진다. 가형과 나형의 금액이 같은 경우에도 이 선택 기준을 그대로 적용한다. 주어진 금액과 상자의 수용 한도를 바탕으로 직원이 선택할 가형 묶음 수와 나형 묶음 수를 구한다. 정확한 금액을 만들 수 있더라도 상자에 모두 들어가지 않으면 가능한 구성으로 보지 않는다. 두 조건을 모두 만족하는 구성이 하나도 없다면 준비가 불가능하다는 결과를 출력한다.

입력

첫째 줄에 네 정수 A, B, T, K가 공백으로 구분되어 주어진다.
1 ≤ A, B ≤ 10,000이고, 0 ≤ T ≤ 1,000,000,000이며, 0 ≤ K ≤ 100,000이다. A와 B는 서로 같을 수도 있다.

출력

가능한 구성이 있으면 선택 기준에 따른 가형 묶음 수 x와 나형 묶음 수 y를 공백으로 구분하여 한 줄에 출력한다. 전체 묶음 수가 가장 적어야 하며, 동점이면 x가 가장 작아야 한다. 가능한 구성이 없으면 -1 하나만 출력한다.

6 9 36 6

0 4

7 7 21 5

0 3

4 7 15 2

-1

출처: Devin.KR 자체 제작