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

Fermierul Ion s-a hotarat sa-si vanda lucrul pe care il pretuieste cel mai mult, ferma mostenita de la tatal sau. Aceasta are forma unui triunghi dreptunghic cu catelele de lungime $N$ si este alcatuita din parcele $1x1$. Pentru fiecare parcela Ion stie suma de bani pe care o obtine prin vanzarea ei.
 

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.
 

h2. Cerinta

Fermierul va cere sa ii spuneti profitul maxim pe care il poate obtine in $K$ zile, stiind ca in fiecare zi vinde exact un teren. Un teren poate fi scos la vanzare doar daca este latura a mosiei lui Ion.

Stiind configuratia gradinii, sa se afle recolta maxima pe care o poate obtine Ion, avand la dispozitie k litrii de benzina.

h2. Date de intrare

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.

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 fiecare reprezentand numarul de kilograme de recolta ce pot fi culese de pe parcela respectiva.

h2. Date de ieşire

În fişierul de ieşire $ferma2.out$ se va afisa profitul maxim pe care il poate obtine Ion.

În fişierul de ieşire $ferma2.out$ se va afisa numarul maxim de kilograme pe care le poate obtine Ion.

h2. Restricţii

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

| 5 3
82
55 3
67 46 52
62 20 54 85
66 32 40 78 52
| 702

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

|

h3. Explicaţie
 
...
 

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