== include(page="template/taskheader" task_id="pokemon") ==
Poveste şi cerinţă...
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{~ij~}$ puncte iar pokemasterul care deţine pokemonul $j$ va primi $a{~ji~}$ 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.
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.
h2. Date de intrare
Fişierul de intrare $pokemon.in$ ...
Î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 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.
h2. Date de ieşire
În fişierul de ieşire $pokemon.out$ ...
Î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.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $4 ≤ N ≤ 50$
* $1 ≤ M ≤ 100$
* $a{~ij~} ≤ 100.000.000$
* Pentru $40%$ din teste $N ≤ 35$ şi $M ≤ 40$
h2. Exemplu
table(example). |_. pokemon.in |_. pokemon.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 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
|
h3. 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.
== include(page="template/taskfooter" task_id="pokemon") ==
