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

Jocul nostru presupune parcurgerea unui tablou bidimensional cu două linii şi $N$ coloane, format din $2 x N$ celule pătratice. Fiecare celulă are asociată câte o valoare întreagă $v$ care nu se modifică pe durata desfăşurării jocului. Jucătorii  trebuie să găsească un drum de la celula de plecare la celula de sosire care  respectă următoarele condiţii:

Jocul nostru presupune parcurgerea unui tablou bidimensional cu două linii şi $N$ coloane, format din $2 x N$ celule pătratice. Fiecare celulă are asociată câte o valoare întreagă $v$ care nu se modifică pe durata desfăşurării jocului. Jucătorii trebuie să găsească un drum de la celula de plecare la celula de sosire care respectă următoarele condiţii:

* celula de plecare este cea din linia $1$ şi coloana $1$, iar celula de sosire este cea din linia $2$ şi coloana $N$.

* nu trece decât cel mult odată prin oricare celulă.

* nu trece decât cel mult o dată prin oricare celulă.

* deplasarea se poate face din celula curentă spre oricare altă celulă învecinată cu ea pe orizontală sau verticală.
* conţine cel mult $K$ celule consecutive aflate pe aceeaşi linie.

h2. Date de intrare

Fişierul de intrare $joc13.in$ va conţine pe prima linie două numere naturale $N$ şi $K$ separate printr-un  spaţiu cu semnificaţiile din enunţ. Pe fiecare dintre următoarele două linii se găsesc câte $N$ numere întregi, reprezentând valorile asociate celor $2 x N$ celule ale tabloului.

Fişierul de intrare $joc13.in$ va conţine pe prima linie două numere naturale $N$ şi $K$ separate printr-un spaţiu cu semnificaţiile din enunţ. Pe fiecare dintre următoarele două linii se găsesc câte $N$ numere întregi, reprezentând valorile asociate celor $2 x N$ celule ale tabloului.

h2. Date de ieşire

h2. Restricţii
* $2 ≤ N ≤ 5000$

* $2 ≤ K ≤ 10, K ≤ N$

* $2 ≤ K ≤ 10, K ≤ N$

* $-1000 ≤ v ≤ 1000$

* Pentru $40%$ dintre cazurile de test $N ≤ 40$

* Pentru $40%$ dintre cazurile de test $N ≤ 40$.

h2. Exemplu

| 21
| !problema/joc13/?1.bmp!
|

 
 
table(example). |_. joc13.in |_. joc13.out |_. Explicaţie |

| 5 5
0 0 4 2 10
2 -3 -8 6 -2
| 14
| !problema/joc13/?2.bmp!
|

 
 
table(example). |_. joc13.in |_. joc13.out |_. Explicaţie |

| 5 4
-3 0 5 4 10
-2 3 -2 7 0

4619