== include(page="template/taskheader" task_id="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ă din colier. 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)$.

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

h2. Cerinta

Determinaţi valoarea maximă ce o poate avea o subsecvenţa din şirul dat.

Determinaţi valoarea maximă posibilă a unei subsecvenţe din şirul dat.

h2. Date de intrare