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

Vezi solutiile trimise | Statistici

Perle2

Laura a primit un colier de 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.

Date de intrare

Fişierul de intrare perle2.in conţine pe prima linie două numere întregi N şi K. Pe a doua linie se găsesc N numere întregi reprezentând 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
• Pentru 30% din teste, N ≤ 1 000.

Exemplu

Explicaţie

Subsecvenţa de valoare maximă este [2, 3].

Cum se trimit solutii?