Fişierul intrare/ieşire:	perle2.in, perle2.out	Sursă	Algoritmiada 2010, Runda 1
Autor	Paul-Dan Baltescu	Adăugată de	Paul-Dan Baltescu •pauldb
Timp execuţie pe test	0.025 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Perle2

Laura a primit un colier cu N perle. Ea a reprezentat într-un vector A de numere întregi cât de mult îi place fiecare perlă din colier. Mai exact, valoarea de pe poziţia i din vector ne spune cât de mult îi place Laurei cea de a i-a perlă. Ea şi-ar dori să păstreze o subsecvenţă de perle din colier care să-i placă cât mai mult, dar este conştientă că şi lungima subsecvenţei alese afectează frumuseţea colierului cu un factor K cunoscut. De aceea, fata vă roagă să găsiţi o subsecvenţă [i, j] care maximizează valoarea (A_i + A_i+1 + ... + A_j) - K*(j-i+1).

Cerinta

Determinaţi valoarea maximă posibilă a unei subsecvenţe din şirul dat. Pe următoarele N linii se găseşte câte un număr întreg din vectorul A.

Date de intrare

Fişierul de intrare perle2.in conţine pe prima linie două numere întregi N şi K. Pe următoarele N linii se află câte un număr întreg reprezentând câte un element din vectorul A.

Date de ieşire

În fişierul de ieşire perle2.out conţine un singur număr întreg ce corespunde valorii cerute.

Restricţii

1 ≤ N ≤ 100 000
-10 000 ≤ K ≤ 10 000
-10 000 ≤ A_i ≤ 10 000
Dacă valoarea maximă posibilă este negativă, atunci Laura va prefera sa nu aleagă nici o perlă.
Pentru 30% din teste, N ≤ 1 000.