!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$ si $K$. Pe urmatoarele $N$ linii este data configuratia gradinii: linia $i + 1$ va contine $i$ numere fiecare reprezentand valoarea parcelei respective.

* $1 ≤ N ≤ 1000$
* $0 ≤ K ≤ N$

* $0 ≤ profitul obtinut de Ion pentru o parcela 1x1 ≤ 100$

* $0 ≤ profitul obtinut de Ion pentru un patrat 1x1 ≤ 100$

h2. Exemplu