사내 메신저의 알림 묶음

문제

사내 메신저의 운영 담당자는 여러 팀에 전달할 알림을 준비하고 있다. 이번 안내에서는 각 팀에 같은 수의 일반 알림을 보내고, 그와 별도로 공용 게시판에 추가 알림을 보낸다. 메신저 서버는 준비된 알림을 한꺼번에 처리하지 않고, 정해진 개수 이하의 알림을 묶어 요청 단위로 처리한다. 팀의 수를 A, 각 팀에 보낼 일반 알림의 수를 B, 공용 게시판에 보낼 추가 알림의 수를 C라고 한다. 일반 알림은 팀마다 따로 보내므로 전체 일반 알림의 수는 A와 B의 곱이다. 공용 게시판의 추가 알림은 모든 팀을 합쳐 C개만 준비한다. 따라서 추가 알림의 수에 팀의 수를 다시 곱하지 않는다. 한 번의 처리 요청에는 알림을 최대 K개까지 담을 수 있다. 모든 알림을 처리하는 데 필요한 요청 횟수를 가장 적게 만들려고 한다. 서로 다른 팀에 보내는 알림과 공용 게시판에 보내는 알림을 같은 요청에 담아도 된다. 알림의 순서나 종류에 따른 제한은 없으며, 알림 하나를 여러 요청으로 나눌 수는 없다. 마지막 요청에 담긴 알림의 수가 K보다 작아도 정상적으로 처리된다. 전체 알림의 수가 K의 배수라면 빈 요청을 추가하지 않는다. 일반 알림과 추가 알림이 모두 없어서 전체 알림의 수가 0이면 요청을 전혀 보내지 않으므로 필요한 횟수도 0이다. 요청 한 번에 담을 수 있는 최대 개수는 항상 양의 정수다. 알림을 보내는 데 걸리는 시간이나 수신자의 수는 계산하지 않는다. 주어진 네 정수로 전체 알림의 수를 구한 뒤, 이를 모두 처리하기 위한 최소 요청 횟수를 계산하는 프로그램을 작성한다. 결과는 소수나 분수 없이 정수로 출력한다.

입력

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

출력

모든 알림을 처리하기 위한 최소 요청 횟수를 정수 하나로 출력한다. 처리할 알림이 없으면 0을 출력한다.

7 4 3 10

4

6 3 6 8

3

9 0 0 5

0

출처: Devin.KR 자체 제작