지원 키트 상자 주문

문제

사내 IT 지원실은 새 작업 공간에 설치할 지원 키트를 준비한다. 지원 키트 한 개에는 연결 케이블과 간단한 안내 카드가 들어 있다. 이번에 준비할 작업 공간은 B곳이며, 각 공간에는 지원 키트를 정확히 C개씩 배치해야 한다. 모든 공간의 배치를 마칠 때 필요한 지원 키트의 총개수는 B와 C의 곱이다. 지원실에는 이전 작업에서 남은 지원 키트 A개가 있다. 보관 중인 키트는 모두 사용할 수 있으며, 새로 구입한 키트와 구별하지 않고 배치한다. 먼저 보관 중인 키트를 사용하고, 필요한 수량보다 보관 수량이 적을 때만 추가 주문한다. 보관 수량만으로 충분하다면 추가 주문을 하지 않는다. 공급 창고에서는 지원 키트를 낱개로 판매하지 않는다. 상자 하나에는 지원 키트가 정확히 P개 들어 있으며, 주문하는 상자 수는 0 이상의 정수여야 한다. 주문한 상자는 모두 도착한 뒤 개봉할 수 있고, 한 상자의 키트를 여러 공간에 나누어 배치해도 된다. 따라서 각 공간에 상자를 따로 배정할 필요는 없다. 필요한 키트를 모두 배치할 수 있도록 하면서 주문하는 상자 수를 가장 작게 정한다. 배치를 마친 뒤 남은 키트는 다시 지원실에 보관한다. 남은 개수에는 기존에 보관하던 키트와 새 상자에서 꺼낸 키트를 모두 포함한다. 주문할 최소 상자 수와, 그 수의 상자를 주문하여 모든 배치를 마친 뒤 남는 지원 키트의 개수를 구한다. 필요한 수량과 보관 수량이 같다면 두 값은 모두 0이다.

입력

첫째 줄에 정수 A, B, C, P가 공백으로 구분되어 주어진다. A는 보관 중인 키트 수, B는 작업 공간 수, C는 공간마다 필요한 키트 수, P는 상자 하나에 든 키트 수이다. 0 ≤ A ≤ 1,000이며, 1 ≤ B, C, P ≤ 1,000이다.

출력

주문할 최소 상자 수와 배치를 마친 뒤 남는 키트 수를 공백 하나로 구분하여 한 줄에 출력한다.

7 4 6 5

4 3

40 3 8 6

0 16

0 2 9 6

3 0

출처: Devin.KR 자체 제작