rau

Peste un mic râu care se varsă într-un mare râu, într-un oraș din inima munților, există $N$ pietre, numerotate de la $1$ la $N$. Un grup de copii obișnuiește să nu aleagă calea ușoară, așa că trebuie să sară peste cele $N$ pietre, pentru a ajunge pe partea cealaltă.

Pentru fiecare dintre aceste pietre, se cunoaște înălțimea sa, notată, în continuare, $h\lbrack i\rbrack$ . Prietenii pot să aleagă să sară anumite pietre, pentru a minimiza efortul necesar traversării râului. Formal, de pe piatra cu indicele$i$, aceștia pot să ajungă pe toate pietrele numerotate cu indicii $i + 1,\ i + 2\ ..\ min(N, i + K)$. Efortul necesar pentru a sări de pe piatra $i$ pe piatra$\text{\ j}$de este dat de formula $\lbrack\sqrt[3]{abs(h\lbrack i\rbrack\ - \ h\lbrack j\rbrack\rbrack)}\rbrack\ + \ C$, unde $C$este o constantă.

Cerință

Să se calculeze efortul minim de a ajunge de la prima piatră la ultima.

Date de intrare

Pe prima linie din fișierul rau.in se află trei numere naturale $N,\ K,\ C$.
Pe a doua linie din fișierul de intrare se află numerele $h\lbrack i\rbrack$, pentru i de la $1$ la $N$.

Date de ieșire

Fişierul de ieşire rau.out va conţine efortul minim calculat.

Restricții și precizări

• $1 \le K < N \le 5 *\ 10^{4},\ 1 \le C \le 10{}^{4}$
• $1 \le \ h\lbrack i\rbrack\ \le \ 4\ *\ 10^{5}$
• Pentru calculul rădăcinii de ordin 3, se poate folosi $cbrt(double)$ din biblioteca $\text{cmath}$, în $C + +$
• Pentru $15\%$ din teste, $N\ \le \ 1000$
• Pentru alte $25\%$ din teste, $N\ *\ max(h\lbrack i\rbrack)\ \le 10^{7}\$și $K\ = \ N\ - \ 1$

Exemplu

rau.in

5 2 1        
4 12 37 10 10

rau.out

6

Explicație

Drumul este : 4 -> 12 -> 10 - > 10.

Costul de a ajunge pe 12 este $\lbrack\sqrt[3]{8}\rbrack\ + \ 1\ = \ 3$

Costul de a ajunge pe 10 este $\lbrack\sqrt[3]{2}\rbrack\ + \ 1\ = \ 2$

Costul de a ajunge pe ultimul 10 este $\lbrack\sqrt[3]{0}\rbrack\ + \ 1\ = \ 1$

Drumul 4 -> 37 -> 10 ar fi, 4 + 4 = 8