Comoara

Cei $K$ membri ai unui grup de căutători de comori se află într-un complex dreptunghiular format din camere pătrate de latură $1$. În mod normal toate camerele ar trebui să fie deschise, dar o parte dintre ele sunt închise şi pot fi deschise doar cu ajutorul unor cartele speciale. Astfel, fiecare cameră şi fiecare cartelă are asociat un număr între $0$ şi $20$; o cameră cu numărul asociat $0$ este deschisă de la început, în timp ce una cu numărul asociat diferit de $0$ este iniţial închisă, poate fi deschisă din interior sau din exterior dintr-o cameră vecină cu o cartelă cu numărul corespunzător şi va rămâne deschisă ulterior. Cartelele cu numărul asociat $0$ nu au nici o întrebuinţare practică. Un număr poate fi asociat mai multor cartele, respectiv camere.

Dintr-o cameră se poate trece în alta numai dacă ele sunt vecine şi ambele sunt deschise. Două camere se consideră vecine dacă au un perete (deci o latură) în comun. În fiecare cameră se află comori cu o valoare între $0$ şi $10 \ 000$. De asemenea, în fiecare cameră se află exact o cartelă de acces (cu numărul asociat între $0$ şi $20$); un căutător de comori poate ridica şi folosi cartelele din camerele prin care trece, dar nu le poate da unui alt căutător decât dacă respectivul se află în aceeaşi cameră cu el.

Cerinţă

Cunoscându-se configuraţia complexului şi poziţiile iniţiale ale căutătorilor de comori, să se determine valoarea maximă a comorilor adunate de aceştia.

Date de intrare

Datele de intrare se citesc din fişierul comoara.in care are următorul format:

• pe prima linie dimensiunile complexului, $m$ şi $n$
• pe următoarele $m$ linii numerele asociate fiecărei camere
• pe următoarele $m$ linii valorile comorilor din fiecare cameră
• pe următoarele $m$ linii numerele asociate cartelelor din fiecare cameră
• pe următoarea linie numărul $K$ al membrilor grupului
• pe următoarele $K$ linii poziţiile iniţiale ale membrilor grupului în complex

Date de ieșire

În fişierul comoara.out se va afişa valoarea totală a comorilor care pot fi strânse de cei $K$ membri ai grupului.

Restricții și precizări

• $1 \leq m, n \leq 40$;
• $1 \leq k \leq 10$;

Exemplul 1

comoara.in

3 3
0 0 11
14 0 10
19 0 0
5162 4331 1390
5230 1955 9796
5507 6210 1021
0 0 0
19 0 0
0 0 0
2
3 2
2 1

comoara.out

23909

Explicație

Se observă că al doilea căutator de comori nu poate pătrunde în camera ($3,1$), deşi are cartela corespunzătoare, pentru că nu poate părăsi camera ($2,1$) în care este plasat iniţial)

Exemplul 2

comoara.in

5 5
0 0 2 0 0
0 0 2 0 0
0 0 1 0 0
0 0 2 0 0
0 0 2 0 0
1 1 1 1 1 
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
1 0 0 0 0
1
1 1

comoara.out

21