라바패들링

Lav는 화산 속에서 사악한 마녀에게 붙잡혀 마녀를 위해 임무를 수행해야 한다.

화산 속 거대한 용암 바다에는 $N$개의 섬이 일직선으로 늘어서 있다. $i$번째 섬과 $i+1$번째 섬 사이의 거리는 $d_i$이다. 거리는 "마녀미터"라는 단위로 주어지며, 1마녀미터는 정확히 $H$미터이다. 마녀는 일렬로 늘어선 섬 중 첫 번째 섬에 살고 있고, Lav는 지금 그곳에 있다.

마녀는 일렬로 늘어선 섬 중 마지막 섬에 모든 주문이 적힌 책을 두고 왔고, Lav는 그곳에 가서 책을 가져와야 한다. Lav에게는 용암 배 한 척과 여러 개의 노가 있다. 각 노는 $K$번 젓기 전까지 버틸 수 있으며, 한 번 저을 때마다 배는 1미터 앞으로 나아간다. 그 후 노는 용암 때문에 타 버린다. Lav는 마녀에게서 여러 개의 노를 받으며, 하나의 노를 완전히 다 쓸 때까지 기다렸다가 다른 노로 바꿀 필요는 없다.

또한 Lav는 마녀에게서 주문 하나를 받아 섬 위에 서 있을 때 사용할 수 있다. 이 주문은 조금 저었지만 완전히 타지 않은 노를 고쳐 준다. 그러면 그 노로 다시 $K$미터를 저을 수 있다. Lav는 섬 위에 서 있을 때 이 주문을 원하는 만큼 사용할 수 있다. Lav가 임무를 완수할 수 있도록 마녀가 Lav에게 주어야 하는 노의 최소 개수는 몇 개인가?

첫째 줄에 세 정수 $1 \le N \le 20$ (섬의 개수), $1 \le K \le 15$ (노 하나로 저을 수 있는 미터 수, 즉 노가 타 버리기 전까지 저을 수 있는 횟수), $1 \le H \le 10^{12}$ (1마녀미터에 해당하는 미터 수)가 주어진다. 둘째 줄에는 $N-1$개의 정수 $1 \le d_1, d_2, \dots, d_{n-1} \le 1000$이 주어지며, 이는 일렬로 늘어선 이웃한 섬 사이의 거리이다.

Lav가 임무를 완수할 수 있도록 마녀가 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개보다 적으면 불가능하다.