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

Poveste şi cerinţă...

Andrei este pasionat de drumeţii montane. Într-o astfel de călătorie ajunge la un moment dat să urce un deal sub formă de triunghi isoscel. Din propria experienţă ştie că dealul se urcă cel mai uşor în zig zag pornind de la mijlocul bazei lui.
Dacă ar împărţi dealul în linii, iar liniile în coloane, ar obţine puncte intermediare notate de la 1 la n*n, pornind cu notarea din vârf, iar n fiind numărul de linii. Pentru a ajunge dintr-un punct în altul el cheltuieşte o anumită cantitate de energie. Andrei doreşte să urce dealul în zig zag de la bază spre vârf cu un consum minim de energie. El poate porni spre stânga sau spre dreapta, iar întoarcerea în zig zag o poate efectua după un anumit număr de paşi k. Pornind de pe mediană, după o întoarcere la stânga (sau la dreapta) el parcurge 2*k paşi şi ajunge înapoi pe mediană.
Un deal cu 5 linii şi exemplu de drum cu k=1:
 
==code(c) |
        |3|
      |3| 5 2
    7 2 |5| 6 4
  6 8 |2| 7 4 3 3
3 6 8 9 |0| 3 3 3 3
==
 
Mergând spre stânga (drumul ilustrat), Andrei consumă 0+2+5+3+3 = 13 unităţi de energie, iar spre dreapta 0+4+5+2+3 = 14 unităţi de energie.
 
Cerinţă
Cunoscând efortul pe care il face Andrei pentru a trece prin toate punctele intermediare, se cere efortul minim pentru urcarea dealului, o întoarcere efectuîndu-se după k paşi.

h2. Date de intrare

Fişierul de intrare $zigzag.in$ ...

Fişierul de intrare $zigzag.in$ conţine pe prima linie numărul natural N, reprezentând numărul de linii şi numărul k. Linia următoare conţine N2 numere naturale mai mici decât 500, al i-lea număr reprezentând efortul lui Andrei de a ajunge în punctul intermediar cu numărul i.

h2. Date de ieşire

În fişierul de ieşire $zigzag.out$ ...

Fişierul de ieşire $zigzag.out$ va conţine pe prima linie efortul minim efectuat de Andrei pentru a urca dealul, pornind fie spre stânga, fie spre dreapta.
 
h2. Restricţii şi precizări
 
* 1 < N ≤ 501, N număr impar;
* Punctul de plecare este de fiecare dată mijlocul bazei triunghiului şi are efortul 0;
* 1≤k≤N/2;
* Dacă la un moment dat nu se mai pot efectua k paşi pentru o întoarcere, se va efectua un număr de paşi egal cu cel mai mare număr apropiat de k care permite să ajungem în vârful dealului prin întoarceri succesive. Dacă notăm cu k1 acest număr, Andrei va efectua mai întâi k paşi cât se poate şi apoi k1 paşi până în vârf. Nu sunt permise decât maxim 2 valori pentru pas;
* 20% din testele de intrare au numere n şi k alese astfel încât întoarcerea se face după k paşi de fiecare dată;
 
 
h2. Exemplu
 
table(example). |_. zigzag.in |_. zigzag.out |
| 5 1
3 3 5 2 7 2 5 6 4 6 8 2 7 4 3 3 3 6 8 9 0 3 3 3 3
| 13
|

h2. Restricţii

h3. Explicaţie

* $... ≤ ... ≤ ...$

Triunghiul este cel din text. Spre stânga efortul este 13, iar spre dreapta 14.

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

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

| 7 2
2 2 4 3 5 3 2 1 7 4 3 2 7 5 4 8 5 2 2 6 3 6 1 9 12 4 4 3 1 6 8 5 4 3 9 7 9 4 5 2 1 3 0 2 6 5 8 5 9
| 16

|
h3. Explicaţie

...

==code(c) |
            |2|
          |2| 4 3
        5 3 |2| 1 7
      4 3 |2| 7 5 4 8
    5 2 |2| 6 3 6 1 9 12
  4 4 3 1 |6| 8 5 4 3 9 7
9 4 5 2 1 3 |0| 2 6 5 8 5 9
==
 
Prin stânga drumul este:
0,6,2,2,2,2,2 şi are costul 16, iar prin dreapta 0,5,1,5,2,3,2 cost 18. La linia 3, pasul devine 1.

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