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

IMAGINE
 
 
 
 
	Spre stănga		Spre dreapta
Mergând spre stânga, 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.

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.

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

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

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

Punctul intermediar 1 are efortul 3, al doilea are 3,…al 25-lea are efortul 3.

| 13
|

|
h3. Explicaţie

NU RESPECTA ALINIEREA...........
            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

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