== include(page="template/taskheader" task_id="necromancer") ==

Poveste şi cerinţă...

În urbea $X$ au avut loc alegeri la care au participat $K$ candidaţi. Fiecare cetăţean din cei $N$ ai urbei s-a prezentat la scrutin şi a scris o permutare $p{~1~}, p{~2~}, ..., p{~K~} pe buletinul de vot, reprezentând lista candidaţilor în ordinea preferinţelor cetăţeanului. Va câştiga alegerile candidatul care se află de cele mai multe ori pe poziţia $1$ în cele $N$ permutări introduse în urna de vot.

h2. Date de intrare

Necromancerul doreşte să câştige candidatul cu numărul $1$, Charles. În acest scop, el a reuşit să afle, pentru fiecare votant $i$ din cei $N$, câte un şir $A{~i~}$ care este subşir al permutării $i$ introduse în urna de vot. Necromancerul poate apoi să creeze, prin mijloace numai de el ştiute, voturi suplimentare pentru candidatul $1$.
Ştiindu-se, pentru fiecare permutare $i$ din urnă, câte un subşir $A{~i~}$ al acesteia, se cere să se determine care este numărul minim de voturi suplimentare care trebuie create de Necromancer pentru ca să existe cel puţin un set valid de voturi în care câştigă candidatul $1$, ajutat desigur şi de voturile suplimentare. Un set de voturi este valid dacă, pentru fiecare cetăţean $i$ este aleasă o permutare care conţine şirul $A{~i~}$ ca subşir.

Fişierul de intrare $necromancer.in$ ...

h2. Date de intrare
Fişierul $necromancer.in$ va conţine pe prima linie două numere naturale $N$ şi $K$ cu semnificaţia din enunţ. Pe următoarele $N$ linii se află subşirurile celor $N$ permutări, ştiute de Necromancer. Linia $i+1$ va conţine un număr întreg $L{~i~}$, reprezentând lungimea subşirului. Apoi, linia $i+1$ va mai conţine $L{~i~}$ numere naturale reprezentând elementele subşirului.
 

h2. Date de ieşire

În fişierul de ieşire $necromancer.out$ ...

Fişierul $necromancer.out$ va conţine pe singura linie un număr natural $V$ reprezentând numărul minim de voturi suplimentare necesare pentru a exista cel puţin un set valid de voturi în care candidatul $1$ câştigă.

h2. Restricţii

h2. Restricţii şi precizări

* $... ≤ ... ≤ ...$

* $1 ≤ N, K ≤ 1 000$
* Pentru $30%$ din teste, $1 ≤ N, K ≤ 100$
* Pentru $60%$ din teste, $1 ≤ N, K ≤ 500$
* Candidatul $1$ trebuie să aibă strict mai multe voturi ca următorul clasat pentru a câştiga.

h2. Exemplu
table(example). |_. necromancer.in |_. necromancer.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie

| 3 4
2 3 1
3 2 1 3
4 1 2 3 4
| 1 |
 
h2. Explicaţie
 
Putem alege permutările:
$
3 2 1 4
2 1 3 4
1 2 3 4
$
 
În această situaţie, candidaţii $1$, $2$ şi $3$ au fiecare $1$ vot. Astfel, Necromancerul mai are nevoie să adauge un singur vot suplimentar pentru ca $1$ să aibă două voturi şi să câştige.
 
Observăm că am putea alege neconvenabil permutările:
$
2 3 4 1
2 1 3 4
1 2 3 4
$
În acest caz, candidatul $2$ ar fi avut $2$ voturi şi candidatul $1$ doar $1$ vot. Astfel, Necromancerul ar fi trebuit să adauge $2$ voturi suplimentare.

...

== include(page="template/taskfooter" task_id="necromancer") ==