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 cu h[i]. 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 j este dat de formula \( \left[ \sqrt[ 3 ]{h[i]-h[j]} \right] + C \), unde C este o constantă.

Cerința

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[i], 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 ≤ K < N ≤ 50.000, 1 ≤ C ≤ 10.000
• 1 ≤ h[i] ≤ 400.000
• Pentru calculul rădăcinii de ordin 3 se poate folosi cbrt(double) din biblioteca cmath, în C++
• Pentru 15% din teste, N ≤ 1000
• Pentru alte 25% din teste, N * max(h[i]) ≤ 10.000.000 ș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 \( [\sqrt[ 3 ]{8}] + 1 = 3\).
Costul de a ajunge pe 10 este \( [\sqrt[ 3 ]{2}] + 1 = 2\).
Costul de a ajunge pe ultimul 10 este \( [\sqrt[ 3 ]{0}] + 1 = 1\).
Drumul 4 -> 37 -> 10 ar fi 4 + 4 = 8