메신저의 읽지 않은 알림 카드

문제

사내 메신저에는 읽지 않은 메시지를 모아서 보여 주는 알림 카드 기능이 있다. 직원이 업무를 시작할 때 읽지 않은 메시지는 A개였다. 그 뒤 새로운 메시지가 B개 도착했고, 직원은 기존 메시지와 새 메시지를 합친 것 중 서로 다른 C개의 메시지를 읽었다. 메시지를 읽으면 그 메시지는 읽지 않은 메시지 목록에서 즉시 빠진다. 이 과정에서 메시지가 삭제되거나 다른 메시지가 추가되는 일은 없다. 메신저는 이 과정이 모두 끝난 뒤 남아 있는 읽지 않은 메시지로 알림 카드를 새로 만든다. 알림 카드 한 장에는 메시지를 최대 K개까지 넣을 수 있다. 모든 읽지 않은 메시지는 정확히 한 장의 카드에 들어가야 하며, 같은 메시지를 여러 카드에 넣을 수 없다. 카드에 들어가는 메시지의 순서는 상관없다. 비어 있는 카드는 만들지 않으며, 필요한 카드 수가 가장 적도록 메시지를 나누어 담는다. 예를 들어 읽지 않은 메시지가 11개 남았고 카드 한 장에 최대 4개를 넣을 수 있다면, 메시지를 각각 4개, 4개, 3개 담은 카드 세 장으로 모두 표시할 수 있다. 두 장에는 최대 8개만 담을 수 있으므로 카드 세 장이 필요하다. 마지막 카드에는 K개보다 적은 메시지가 들어가도 된다. 이미 읽은 메시지를 위한 카드는 만들지 않는다. 읽지 않은 메시지가 하나도 남지 않았다면 필요한 카드 수도 0이다. 또한 직원이 읽은 메시지 수 C는 처음 있던 메시지와 새로 도착한 메시지의 총개수를 넘지 않는다. 처음 메시지가 없거나 새 메시지가 도착하지 않은 경우도 주어질 수 있다. A, B, C, K가 주어질 때, 마지막에 남은 읽지 않은 메시지 수와 이를 모두 표시하는 데 필요한 최소 알림 카드 수를 구한다.

입력

첫째 줄에 네 정수 A, B, C, K가 공백으로 구분되어 주어진다. 0 ≤ A ≤ 1,000, 0 ≤ B ≤ 1,000, 0 ≤ C ≤ A+B, 1 ≤ K ≤ 1,000이다.

출력

첫째 줄에 마지막에 남은 읽지 않은 메시지 수와 필요한 최소 알림 카드 수를 순서대로 공백으로 구분하여 정수로 출력한다. 읽지 않은 메시지가 없으면 두 값 모두 0을 출력한다.

8 7 4 4

11 3

3 6 9 5

0 0

12 8 4 8

16 2

출처: Devin.KR 자체 제작