Fişierul intrare/ieşire:	zigzag.in, zigzag.out	Sursă	ad-hoc
Autor		Adăugată de	CCEX2015 •CCEX2015
Timp execuţie pe test	0.15 sec	Limită de memorie	12288 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Zigzag

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:

|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.

Date de intrare

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.

Date de ieşire

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.

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ă;

Exemplu

Explicaţie

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

Exemplu

Explicaţie

|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.

Cum se trimit solutii?