== include(page="template/taskheader" task_id="ferma2") ==
Fermierul Ion a achizitionat un nou teren in forma de triunghi dreptunghic format din parcele 1x1. El are la dispozitie un vehicul care poate culege toata recolta de pe o latura cu un litru de benzina. Dupa culegerea uneia dintre laturi, aceasta nu mai face parte din triunghi.
Criza l-a lovit inclusiv pe batranul nostru prieten, fermierul Ion. Ramanand fara banii necesari intretinerii fermei, s-a hotarat sa vanda parcele in decursul a $K$ zile. Terenul lui Ion este de forma unui triunghi dreptunghic isoscel de cateta $N$, alcatuit din patrate $1x1$, fiecare dintre acestea avand valori diferite la vanzare.
h2. Cerinta
Fiindu-i frica de FISC, fermierul s-a hotarat sa vanda exact o parcela pe zi. Pentru a nu atrage atentia vecinilor, parcela trebuie sa fie una din laturile terenului actual, dupa cum este prezentat in figura de mai jos:
Stiind configuratia gradinii, sa se afle recolta maxima pe care o poate optine Ion avand la dispozitie k litrii de benzina.
!problema/ferma2?ferma2.jpg!
Ajutati-l pe prietenul nostru sa obtina din vanzarea parcelelor profitul maxim posibil, fara ca FISC-ul sau vecinii invidiosi sa-l detecteze.
h2. Date de intrare
Fişierul de intrare $ferma2.in$ va contine pe prima linie numerele N( dimensiunea gradinii) si K( numarul de litrii de benzina pe care fermierul Ion ii are la dispozitie). Pe urmatoarele N linii este data configuratia gradinii: linia i + 1 va contine i numere ce reprezinta numar de kilograme de recolta de pe parcela respectiva.
Fişierul de intrare $ferma2.in$ va contine pe prima linie numerele $N$ si $K$. Pe urmatoarele $N$ linii este data configuratia gradinii: linia $i + 1$ va contine $i$ numere fiecare reprezentand valoarea parcelei respective.
h2. Date de ieşire
În fişierul de ieşire $ferma2.out$ se va afisa numarul maxim de kilograme pe care le poate optine Ion.
În fişierul de ieşire $ferma2.out$ se va afisa pe prima linie profitul maxim pe care il poate obtine Ion.
h2. Restricţii
* $1 ≤ N ≤ 1000$
* $0 ≤ K ≤ N$
* $0 ≤ profitul obtinut de Ion pentru un patrat 1x1 ≤ 100$
h2. Exemplu
table(example). |_. ferma2.in |_. ferma2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 5 3
82
55 3
67 46 52
62 20 54 85
66 32 40 78 52
| 702
|
h3. Explicaţie
h2. Explicatie
...
In prima zi Ion vinde parcela cu valorile: $82 55 67 62 66$. In a doua zi el vinde parcela: $3 52 85 52$. In ultima zi vinde: $46 54 78$. Profitul total obtinut este $82 + 55 + 67 + 62 + 66 + 3 + 52 + 85 + 52 + 46 + 54 + 78 = 702$.
== include(page="template/taskfooter" task_id="ferma2") ==
