ktown

Ktown

== include(page="template/taskheader" task_id="ktown") ==

Î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).

Î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.
h2. 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.

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.

h2. Date de ieşire

h2. Restricţii

1 <= N <= 3.000
1 <= K <= 1.000.000
-2.200.000.000 <= înălţimea unei clădiri <= 2.200.000.000
Pentru 60% din teste N <= 300
Valoarea lui K a fost stabilită de cercetătorii de la Universitatea Naţională din Tecuci, după lungi dezbateri

* $1 ≤ N ≤ 3.000$
* $1 ≤ K ≤ 1.000.000$
* $-2.200.000.000 ≤ înălţimea unei clădiri ≤ 2.200.000.000$
* Pentru $60%$ din teste $N ≤ 300$
* Valoarea lui $K$ a fost stabilită de cercetătorii de la Universitatea Naţională din Tecuci, după lungi dezbateri
 

h2. Exemplu
table(example). |_. ktown.in |_. ktown.out |

h3. 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).

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$).

== include(page="template/taskfooter" task_id="ktown") ==

9063