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

Poveste şi cerinţă...

Laura a primit un colier de $N$ perle. Ea a reprezentat intr-un vector $A$ de numere intregi cat de mult ii place fiecare perla din colier. Mai exact, valoarea de pe pozitia $i$ din vector ne spune cat de mult ii place Laurei cea de $i$-a perla din colier. Ea si-ar dori sa pastreze o subsecventa de perle din colier care sa-i placa cat mai mult, dar este constienta ca si lungima subsecventei alese afecteaza frumusetea colierului cu un factor $K$ cunoscut. De aceea, fata va roaga sa gasiti o subsecventa $[i, j]$ care maximizeaza valoarea $(A[i]+A[i+1]+...+A[j]) - K*(j-i+1)$.
 
h2. Cerinta
 
Determinati valoarea maxima ce o poate avea o subsecventa din sirul dat.

h2. Date de intrare

Fişierul de intrare $perle2.in$ ...

Fişierul de intrare $perle2.in$ contine pe prima linie doua numere intregi $N$ si $K$. Pe a doua linie se gasesc $N$ numere intregi reprezentand vectorul $A$.

h2. Date de ieşire

În fişierul de ieşire $perle2.out$ ...

În fişierul de ieşire $perle2.out$ contine un singur numar intreg reprezentand valoarea ceruta.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 100 000$
* $-10 000 ≤ K ≤ 10 000$
* $-10 000 ≤ A{~i~} ≤ 10 000$
* Pentru $30%$ din teste, $N ≤ 1 000$.

h2. Exemplu