pokemon

Pe un tărâm îndepartat, într-un univers paralel, se află cel mai curajos pokemaster, Qwerty. Un pokemaster are trei pokemingi, fiecare pokeminge având câte un pokemon. În lumea pokemonilor există $N$ specii de pokemoni şi niciun pokemon imbatabil. Pokemasterul Qwerty va participa într-un poketurneu de pokelupte organizat la pokeColoseum. Dacă se dă o pokeluptă între oricare doi pokemasteri $A$ şi $B$, atunci atât $A$ cât şi $B$ vor folosi toţi cei trei pokemoni pe care îi are fiecare. Pokemonul din prima pokeminge a lui $A$ se va pokelupta cu pokemonul aflat în prima pokeminge a lui $B$, pokemonul din a doua pokeminge a lui $A$ se va pokelupta cu pokemonul din a doua pokeminge a lui $B$, iar pokemonul din a treia pokeminge a lui $A$ se va pokelupta cu pokemonul din a treia pokeminge a lui $B$. Dacă într-o pokeluptă se va pokelupta pokemonul $i$ cu pokemonul $j$ atunci pokemasterul care deţine pokemonul $i$ va primi $a_{i,j}$ puncte iar pokemasterul care deţine pokemonul $j$ va primi $a_{j,i}$ puncte. O pokeluptă este câştigată de pokemasterul care are cele mai multe puncte. În caz de egalitate nici un pokemaster nu va câştiga acea pokeluptă.

Qwerty ştie că se va pokelupta pe rând cu $M$ pokemasteri şi ştie ce pokemoni au aceştia. El are voie să îşi schimbe oricâţi pokemoni din pokemingi între pokelupte cu pokemoni din colecţia sa. Colecţia sa de pokemoni conţine trei exemplare din toate cele $N$ specii de pokemoni. El ar vrea să câştige toate pokeluptele făcând un numar minim de schimbări de pokemoni.

Cerinţă

Qwerty vă pune la dispoziţie toate datele necesare şi vă oferă $100$ de pokepuncte dacă reuşiţi să aflaţi numărul minim de schimbări pe care trebuie să le facă astfel încât să câştige toate pokeluptele din poketurneul desfăşurat la pokeColoseum.

Date de intrare

În fişierul de intrare pokemon.in pe prima linie se vor afla două numere naturale $N$ şi $M$ reprezentând numărul de pokemoni şi numărul de pokemasteri. Pe a doua linie se vor afla trei numere naturale $P_1$, $P_2$ şi $P_3$ reprezentând pokemonii din pokemingile pe care le are Qwerty la începutul poketurneului. Urmează $N$ linii cu câte $N$ numere naturale reprezentând elementele unei tablou a. Al $j$-lea număr de pe a $i$-a linie reprezintă numărul de puncte pe care le va primi un pokemaster într-o pokeluptă în care el deţine pokemonul $i$ iar adversarul său deţine pokemonul $j$. Urmează $M$ linii cu câte trei numere naturale reprezentând pokemonii adversarilor lui Qwerty.

Date de ieșire

În fişierul de ieşire pokemon.out se va afişa pe prima linie un singur număr natural reprezentând numărul minim de schimbări de pokemoni pe care trebuie să le facă Qwerty astfel încât să câştige toate pokeluptele poketurneului.

Restricții și precizări

• $4 \leq N \leq 50$
• $1 \leq M \leq 100$
• $a_{i,j} \leq 100 \ 000 \ 000$
• Pentru $40\%$ din teste $N ≤ 35$ şi $M ≤ 40$

Exemplu

pokemon.in

4 3 
1 2 3 
7 8 1 2 
2 8 1 9 
7 2 2 1 
3 4 8 6 
4 1 4 
2 3 1 
4 2 4

pokemon.out

3

Explicație

În prima pokeluptă Qwerty îşi va schimba pokemoni din pokemingile $2$ şi $3$ cu pokemonul $3$ respectiv $1$ deoarece dacă nu ar face acest lucru, în lupta $1 \ 2 \ 3$ vs. $4 \ 1 \ 4$ el va avea $5$ puncte iar adversarul său $19$ puncte. În lupta $1 \ 3 \ 1$ vs. $4 \ 1 \ 4$ Qwerty câştigă cu scorul de $11$ la $7$.
În a doua pokeluptă Qwerty păstrează aceaşi pokemoni. În lupta 1 3 1 vs. 2 3 1 Qwerty câştigâ cu scorul de 17 la 11. În ultima pokeluptă Qwerty işi va schimba pokemonul din pokemingea numărul $2$ cu pokemonul $1$. În lupta $1 \ 1 \ 1$ vs. $4 \ 2 \ 4$ Qwerty câştigă cu scorul de $12$ la $8$.
Scenariul de mai sus nu este singurul care garantează numărul minim de schimbări.