necromancer

Î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.

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$.

Cerință

Ș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.

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.

Date de ieșire

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ă.

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.

Exemplu

necromancer.in

3 4
2 3 1
3 2 1 3
4 1 2 3 4

necromancer.out

1

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.