용암 카약

Lav는 화산에 사는 사악한 마녀에게 붙잡혔다. 화산의 광대한 용암 바다에는 긴 일렬로 늘어선 $N$개의 섬이 있다. $i$:번째 섬과 $(i+1)$:번째 섬 사이의 거리는 $d_i$이다. 거리는 정확히 $H$미터에 해당하는 ”마녀미터”라는 단위로 주어진다. 마녀는 이 줄의 첫 번째 섬에 살며, Lav도 현재 그곳에 있다.

마녀는 모든 주문이 적힌 책을 이 줄의 마지막 섬에 두고 왔으며, 이제 Lav에게 가서 책을 가져오라고 강요한다. 이를 위해 Lav에게는 용암 보트와 여러 개의 노가 있다. 각 노는 $K$번의 노 젓기 동안 사용할 수 있고, 한 번 저을 때마다 보트가 앞으로 1미터 이동하며, 그 후에는 용암 때문에 노가 타 버린다. Lav는 마녀에게서 여러 개의 노를 가져가며, 다른 노로 바꾸기 전에 하나의 노를 완전히 소모할 필요는 없다.

또한 Lav에게는 섬에 있을 때 사용할 수 있는 마녀의 주문이 있다. 이 주문은 조금 사용했지만 완전히 타 버리지는 않은 노 하나를 수리한다. 그러면 그 노를 다시 사용해 $K$미터를 저어 갈 수 있다. Lav는 섬에 있을 때 원하는 만큼 주문을 사용할 수 있다.

Lav가 임무를 완수할 수 있도록 마녀가 주어야 하는 노의 최소 개수를 계산하는 프로그램을 작성한다.

배점

제출한 풀이는 여러 테스트 케이스 그룹으로 평가된다. 한 그룹의 점수를 얻으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 배점 | 제한 조건

$1$ |$20$| $K = 1, H \leq 100$

$2$ |$40$| $H = 1$

$3$ |$40$| 추가 제한 조건 없음.

첫째 줄에 정수 $N, K, H$ ($1 \leq N \leq 20, 1 \leq K \leq 15, 1 \leq H \leq 10^{12}$)가 주어진다. 이는 각각 섬의 개수, 노가 타 버리기 전에 그 노로 저어 갈 수 있는 미터 수, 마녀미터 하나에 해당하는 미터 수이다.

둘째 줄에는 줄에서 서로 인접한 섬 사이의 거리인 $N-1$개의 정수 $d_i$ ($1 \leq d_i \leq 1000$)가 주어진다.

Lav가 임무를 완수할 수 있도록 마녀가 주어야 하는 노의 최소 개수를 정수로 출력한다.

첫 번째 예제에는 섬이 두 개 있으며, 그 사이의 거리는 $7$마녀미터로, $7\cdot H = 7\cdot 10=70$미터에 해당한다. 각 노로 최대 $5$번 저을 수 있으므로 $70/5 = 14$개의 노가 필요하다.

두 번째 예제에는 섬이 세 개 있으며, 첫 번째 섬과 두 번째 섬 사이의 거리는 $200$미터이고 두 번째 섬과 세 번째 섬 사이의 거리는 $100$미터이다. 각 노로 $7$번 저을 수 있다. Lav가 $31$개의 노를 가지고 출발해 그중 $14$개를 완전히 사용하고, 남은 $17$개의 노 각각으로 $6$번씩 노를 저으면 $14\cdot 7+6\cdot 17=200$미터를 이동하여 두 번째 섬에 도달할 수 있다. 그러면 노가 $17$개 남으며, 이를 주문으로 수리하면 두 번째 섬에서 세 번째 섬까지 갈 수 있다. $31$개보다 적은 노로는 불가능했을 것이다.