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

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

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

h2. Cerinta

Determinati valoarea maxima ce o poate avea o subsecventa din sirul dat.

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

h2. Date de intrare

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

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

h2. Date de ieşire

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

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

h2. Restricţii

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

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 6 3
2 6 7 1 4 -5
| 7

|
h3. Explicaţie

...

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

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