Problem E
Lavapaddling

Lav är tillfångatagen av en ond häxa i en vulkan och måste nu utföra ett uppdrag åt henne.

I det stora lavahavet i vulkanen ligger $N$ öar på en lång rad. Avståndet mellan den $i$:te och den $i+1$:te ön är $d_ i$. Avstånden är givna i enheten “häxameter”, vilket motsvarar exakt $H$ meter. Häxan bor på den första ön i raden, och det är här Lav befinner sig just nu.

Häxan har glömt sin bok med alla trollformler på den sista ön i raden, och Lav måste åka och hämta den. Till sin hjälp har han en lavabåt och ett antal paddlar. Varje paddel håller för att ta $K$ paddeltag, där varje paddeltag för båten framåt en meter, innan paddeln brunnit upp på grund av lavan. Lav får med sig ett antal paddlar från häxan, och behöver inte göra slut helt på en paddel innan han byter till en annan paddel.

Lav får dessutom med sig en trollformel från häxan som han kan använda när han står på en ö. Trollformeln lagar en paddel som han paddlat lite grann med utan att den brann upp helt. Då kan han återigen använda den för att paddla $K$ meter. Lav kan använda trollformeln hur många gånger han vill när han står på en ö. Vad är det minsta antalet paddlar häxan behöver ge Lav så att han kan klara uppdraget?

Indata

På den första raden står tre heltal: $1 \le N \le 20$ – antalet öar, $1 \le K \le 15$ – antalet meter du kan paddla med en paddel innan den brinner upp och $1 \le H \le 10^{12}$ – antal meter en häxameter motsvarar. På den andra raden står $N-1$ heltal $1 \le d_1, d_2, \dots , d_{n-1} \le 1000$, avstånden mellan intilliggande öar i raden.

Utdata

Programmet ska skriva ut ett heltal: det minsta antalet paddlar häxan behöver ge Lav så att han kan klara av uppdraget.

Poängsättning

För testfall värda 1 poäng gäller det att $K=1$ och $H\le 100$.
För testfall värda ytterligare 2 poäng gäller det att $H=1$.

Förklaring av exempel

I första exemplet finns det två öar, med avstånd 7 häxameter, vilket motsvarar $7\cdot H = 7\cdot 10=70$ meter. Med varje paddel kan han ta max 5 paddeltag, så $70/5 = 14$ paddlar krävs.

I andra exemplet finns tre öar, med 200 meter mellan den första och den andra, och 100 meter mellan den andra och den tredje. Varje paddel kan ta 7 paddeltag. Om Lav börjar med 31 paddlar, använder 14 av dem fullt, och tar 6 paddeltag med de resterande 17 paddlarna, så kommer kan han ta sig $14\cdot 7+6\cdot 17=200$ meter, tillräckligt för att komma till andra ön. Då har han 17 paddlar kvar som han lagar med trollformeln, vilket räcker för att ta sig mellan andra och tredje ön. Det hade inte gått med färre än 31 paddlar.

2 5 10
7

14

3 7 100
2 1

31

5 15 1000000000000
92 43 89 10

6531851851852