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 aij puncte iar pokemasterul care deţine pokemonul j va primi aji 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 număr 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 P1, P2 şi P3 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 tabloului 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

• 4 ≤ N ≤ 50
• 1 ≤ M ≤ 100
• aij ≤ 100 000 000

Exemple

pokemon.in	pokemon.out	Explicaţii
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	3	Î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.

autor: Andrei Paul Puni

propunător: Prof. Emanuela Cerchez

Liceul de Informatică ″Grigore Moisil″

emanuela.cerchez@gmail.com