ktown

Cerință

În oraşul Tecuci există $N$ clădiri situate în linie, fiecare având o anumită înălţime. Datorită riscului ridicat de furtuni cu fulgere în acea zonă, primarul oraşului a stabilit că înălţimile celor $N$ clădiri trebuie modificate astfel încât o clădire să fie mai înaltă cu cel puţin $K$ unităţi decât cea din stânga sa (dacă există o astfel de clădire).
Definim o operaţie asupra unei clădiri ca fiind adăugarea sau scăderea unei unităţi din înalţimea acesteia. Deoarece bugetul primăriei este limitat, primarul doreşte să modifice clădirile în forma dorită cu un număr minim de operaţii. Deoarece doriţi să fiţi făcut cetaţean de onoare al oraşului, voi trebuie să-l ajutaţi pe primar.

Date de intrare

Pe prima linie a fişierului ktown.in se află $N$ şi $K$, numărul de clădiri din Tecuci, respectiv diferenţa minimă dintre o clădire şi cea din stânga sa. Următoarea linie conţine $N$ numere întregi, al $i$-lea din aceste numere reprezentând înălţimea celei de-a $i$-a clădiri.

Date de ieșire

Pe prima (şi singura) linie a fişierului ktown.out trebuie să afişaţi numărul minim de operaţii necesare pentru a modifică înalţimile clădirilor astfel încât să respecte proprietăţile cerute.

Restricții și precizări

• $1 \leq N \leq 3 \ 000$
• $1 \leq K \leq 1 \ 000 \ 000$
• $-2 \ 200 \ 000 \ 000 \leq$ înălţimea unei clădiri $\leq 2 \ 200 \ 000 \ 000$
• Pentru $60\%$ din teste $N \leq 300$
• Valoarea lui $K$ a fost stabilită de cercetătorii de la Universitatea Naţională din Tecuci, după lungi dezbateri

Exemplu

ktown.in

5 1
5 4 3 2 1

ktown.out

12

Explicație

Vom aduce clădirea $1$ la înălţimea $1$ (cu costul $4$), clădirea $2$ la înălţimea $2$ (cu costul $2$), clădirea $3$ la înalţimea $3$ (cu costul $0$), clădirea $4$ la înălţimea $4$ (cu costul $2$) şi clădirea $5$ la înălţimea $5$ (cu costul $4$).