== include(page="template/taskheader" task_id="spargere2") ==
Poveste şi cerinţă...
Georgică este un tip lacom. Jefuirea băncii Georgelonia este o nimica toată pe lângă noul gând măreţ al acestuia. De această dată, Georgică plănuieşte să jefuiască Petrilonia, marea rivală a băncii Georgelonia.
Asemenea băncii Georgelonia, Petrilonia are $N$ seifuri, numerotate de la $1$ la $N$. În fiecare seif $i$ se găseşte o sumă de bani $v[i]$. Pentru că Runda 4 şi pentru că Petrilonia, această sumă de bani nu este neapărat pozitivă. Definim distanţa dintre două seifuri $i$ şi $j$ ca fiind $|i - j|$. Georgică ştie că dacă va deschide două seifuri care se află la distanţă *strict mai mică* decât $K$, se va declanşa alarma. În momentul în care Georgică deschide un seif, este obligat să ia toţi banii din acel seif.
h2. Cerinţă
Georgică se întreabă oare care este suma maximă de bani pe care o poate fura din banca Petrilonia, în timpul Rundei a 4-a, fără să declanşeze alarma.
h2. Date de intrare
Fişierul de intrare $spargere2.in$ ...
Fişierul de intrare $spargere2.in$ conţine pe prima linie două numere naturale $N$ şi $K$, având semnificaţia din enunt. Pe cea de-a doua linie, se vor găsi $N$ numere naturale $v[i]$.
h2. Date de ieşire
În fişierul de ieşire $spargere2.out$ ...
În fişierul de ieşire $spargere2.out$ se va găsi un singur număr natural, reprezentând răspunsul la întrebarea lui Georgică.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ K ≤ N ≤ 100.000$
* $-10^9^ ≤ v[i] ≤ 10^9^$
* $Georgică poate pleca din bancă fără să deschidă vreun seif, în cazul în care această decizie este una înţeleaptă. În acest caz, profitul lui va fi egal cu 0.$
h2. Exemplu
table(example). |_. spargere2.in |_. spargere2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 4 2
1 -1 10 4
| 11
|
h3. Explicaţie
...
Georgică nu are voie să golească două seifuri aflate la distanţă strict mai mică decât $2$. Altfel spus, Georgică nu are voie să golească două seifuri consecutive. Profitul maxim se obţine golind seiful $1$ şi seiful $3$.
== include(page="template/taskfooter" task_id="spargere2") ==
