card

În orașul Imios se află $n$ galerii ce au locații interesante de vizitat (muzee, expoziții, castele), notate de la $1$ la $n$. O galerie conține $m$ locații, notate de la $1$ la $m$. Fiecare locație are atribuit un număr de puncte, unic ca valoare. Orașul are multe birouri de informare turistică, de unde turiștii pot cumpăra un card de o zi pentru vizitarea locațiilor. Pe fiecare card se înregistrează punctul de plecare, notat prin $2$ numere: numărul galeriei si cel al locației, din care se pot vizita cel mult $k$ locații din oraș, diferite de punctul de plecare. Cardul are înregistrat un număr de puncte, ce vor fi utilizate în locațiile vizitate. Alegând o locație ce are $x$ puncte, turistul poate selecta $4$ categorii de vizitare, ce modifică punctele de pe card astfel:

• categoria rapidă: numărul de puncte de pe card se reduce cu dublul lui $x$
• categoria extinsă: numărul de puncte de pe card se reduce cu $\frac{x}{2}$ puncte
• categoria medie: la numărul de puncte de pe card se adaugă $x$ puncte
• categoria clasică: din numărul de puncte de pe card se scad $x$ puncte.

Alexandru a cumpărat un card și dorește să viziteze cât mai puține locații și să utilizeze toate punctele de pe card. Împreună cu cardul, a primit o hartă electronică a locațiilor din oras, codificată printr-o matrice $h$, având $n$ linii și $m$ coloane, pe care este înregistrat numărul de puncte al fiecarei locații. Pe hartă, punctul de plecare, înregistrat pe card, conține numărul de puncte disponibile pe card pentru vizitare. A fost informat că dupa vizitarea unei locații, se poate deplasa numai într-o locație vecină cu aceasta în cele $8$ direcții (N, NE, E, SE, S, SV, V, NV). Fiecare locație poate fi vizitată o singură dată, pe baza cardului.

Alexandru a decis că dacă are mai multe variante posibile de vizitare, din care să aleagă, va opta pentru acea variantă în care ultima locație are cel mai mic număr de puncte. Dacă există mai multe variante de vizitare care au același număr minim de puncte pentru ultima locație, va opta pentru varianta în care prima locație are cel mai mic număr de puncte. Două variante de vizitare diferă prin: locațiile lor, ordinea locațiilor vizitate și categorii de vizitare alese pentru locații.

Cerinţă

Să se scrie un program care obține numărul de variante posibile de vizitare a unor locații din oraș, care conțin cât mai puține locații vizitate din punctul de plecare, ce asigură utilizarea tuturor punctelor de pe card și lista punctelor din locațiile vizitate, în ordinea vizitării lor, pentru varianta pe care Alexandru o alege.

Date de intrare

Fişierul de intrare card.in conţine pe prima linie cinci numere naturale separate prin spaţiu $n, m ,x, y, k$ cu semnificația următoare: $n$ este numărul de linii și m este numărul de coloane din matricea $h$, valorile $x$ și $y$ reprezintă punctul de plecare înregistrat pe cardul lui Alexandu (linia $x$ și coloana $y$ pe hartă), $k$ reprezintă numărul maxim de locații ce pot fi vizitate din punctul de plecare, pe baza cardului. Pe fiecare dintre următoarele $n$ linii se află câte $m$ numere naturale separate prin spaţiu ce reprezintă punctele atribuite locațiilor. Astfel linia $i$ va descrie, în ordine, punctele atribuite celor $m$ locații din galeria $i$.

Date de ieşire

Fişierul de ieşire card.out va conţine pe prima linie un număr natural ce reprezintă numărul de variante posibile de vizitare a unor locații din oraș ce-i permite lui Alexandru utilizarea tuturor punctelor de pe card, în condițiile pe care le-a stabilit.

A doua linie din fișier va conține un șir de numere separate prin câte un spatiu, ce reprezintă lista punctelor din locațiile vizitate în ordinea vizitării lor, pentru varianta pe care Alexandru o alege.

Restricții și precizări

• $2 \leq n,m \leq 30$
• Liniile și coloanele matricii h sunt numerotate de la $1$ și matricea $h$ are elemente distincte
• $0 < h_{i,j} \leq 10^5$, pentru $1 \leq i \leq n$, $1 \leq j \leq m$
• $1 \leq k \leq 6$, $1 \leq x \leq n$, $1 \leq y \leq m$
• Pentru datele de test, există o singură variantă de vizitare ce poate fi selectată în condițiile problemei, dintre variantele posibile de vizitare

Exemplu

card.in

3 4 2 2 3
54 9 11 14
20 34 2 8
7 27 10 29

card.out

10
20 7

Explicație

Alexandru are pe card $34$ de puncte. O variantă de vizitare cu $3$ locații are punctele $(9,11,14)$ și verifică relația $34-9-11-14=0$. El alege din $10$ variante posibile de vizitare, care îi consumă toate punctele de pe card: $(10,29), (27,20), (27,7), (7,27), (10,29), (7,20), (20,7), (20,27),(20,54), (54,20)$. Dintre acestea, el va vizita varianta cu punctele $(20,7)$ ce verifică toate condițiile lui. Varianta $(10,29)$ se selectează de $2$ ori prin categorii de vizitare diferite: $34-\frac{10}{2}-29=0$ și $34-10 \cdot 2-\frac{29}{2}=0$. Varianta $(54,20)$: $34-54+20=0$