Fişierul intrare/ieşire:	ferma.in, ferma.out	Sursă	preONI 2005 Runda 3
Autor	Mircea Bogdan Pasoi	Adăugată de
Timp execuţie pe test	0.15 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	3/5

Vezi solutiile trimise | Statistici

Ferma

Testele pentru aceasta problema nu sunt destul de bine construite pentru a departaja corect solutii ineficiente sau gresite. Intra aici daca vrei sa ne ajuti sa imbunatatim calitatea testelor pentru aceasta problema!

Zaharel s-a dus in vizita la bunicii lui de la tara impreuna cu Eugenia. Ferma bunicilor este de forma circulara, iar acolo cresc N gaini. Ferma a fost impartita in N sectoare, numerotate de la 1 la N, astfel incat oricare doua sectoare avand numere consecutive sunt adiacente (se afla unul langa altul). In plus, primul si ultimul sector sunt adiacente. In fiecare sector se afla cate o gaina, iar aceasta depune oua in fiecare zi. Bunicii stiu pentu fiecare gaina care este productivitatea ei, adica un numar care reprezinta diferenta dintre consumul gainii si cat produce. Zaharel si cu Eugenia strang de K ori pe zi oua de la gaini astfel: la fiecare strangere cei doi aleg o secventa (adica un sir de sectoare adiacente) formata din cel putin un sector, care contine numai gaini de la care nu s-au luat oua in acea zi.

Cerinta

Cunoscand productivitatea fiecarea gaini cat si numarul de strangeri dintr-o zi, ajutati-i pe Zaharel si Eugenia sa stranga oua astfel incat suma productivitatilor gainilor de la care a strans oua sa fie maxima.

Date de Intrare

Pe prima linie a fisierului de intrare ferma.in se gasesc numerele naturale N si K. Pe urmatoarea linie se vor gasi N numere intregi reprezentand productivitatea fiecarei gaini.

Date de Iesire

Pe prima linie a fisierului de iesire ferma.out se va afisa suma maxima posibila a productivitatilor gainilor de la care se strang oua.

Restrictii

• 2 ≤ N ≤ 10.000
• 1 ≤ K ≤ 1.000
• Productivitatea fiecarei gaini este un numar intreg din intervalul [-100.000, 100.000]
• Daca suma maxima posibila a productivitatilor este un numar negativ se va afisa 0 (se prefera sa nu se stranga nici un ou)

Exemplu

Cum se trimit solutii?