Ești în anul 2121 și vrei să configurezi o rețea de Neuralink. Ai la dispoziție N servere, ale căror IP-uri sunt reprezentate de permutări de lungime M (ale numerelor 0, 1 ... M − 1). Vrei ca rețeaua ta să fie cât de mare, dar în același timp, te temi de potențiale probleme de securitate: dacă un hacker află unul dintre IP-uri, îi va fi ușor să găsească un IP similar. Prin urmare, dintre cele N servere pe care le ai la dispoziție, vrei să alegi cât de multe servere pentru rețeaua ta astfel încât să nu existe două servere cu IP-uri similare. Două IP-uri sunt similare, dacă unul dintre ele poate fi obținut din celălalt prin exact o operație swap (o interschimbare a oricăror două elemente). De exemplu, IP-urile (0, 1, 2) și (1, 0, 2) sunt similare, dar (0, 1, 2) și (1, 2, 0) nu.

Date de intrare

Pe prima linie se află numerele N și M. Pe următoarele N linii se vor regăsi câte M numere, elemente ale matricii p. Linia i a matricii p reprezintă cel de-al i-lea IP (o permutare de lungime M).

Date de ieșire

Pe prima linie se va afișa numărul maxim de IP-uri nesimilare.

Restricții și precizări

• 1 ≤ N ≤ 2 500
• 1 ≤ M ≤ 5 000
• Oricare ar fi 0 ≤ i < n, p[i] este o permutare a numerelor de la 0 la M − 1
• Oricare ar fi 0 ≤ i < j < n, p[i] și p[j] sunt distincte

Subtask 1 (11 puncte)

• N, M ≤ 20

Subtask 2 (30 de puncte)

• Cel mult 20 de permutări din cele N sunt similare cu oricare alta dintre cele N
• N ≤ 1000

Subtask 3 (36 de puncte)

• N ≤ 300

Subtask 4 (14 puncte)

• N ≤ 1000

Subtask 5 (9 puncte)

• Fără restricții suplimentare.

Exemple

stdin

3 3
0 1 2
2 1 0
1 0 2

stdout

2

stdin

5 5
0 1 2 3 4
1 0 2 3 4
0 1 2 4 3
0 4 2 3 1
4 1 2 3 0

stdout

4

stdin

6 3
0 1 2
0 2 1
1 0 2
1 2 0
2 1 0
2 0 1

stdout

3

Explicații

Pentru primul exemplu, alegem serverele cu IP-urile (2, 1, 0) și (1, 0, 2). Nu putem alege serverul (0, 1, 2), deoarece IP-ul său este similar cu ale celorlalte 2.

Pentru cel de-al doilea exemplu, putem alege toate IP-urile în afară de primul.

Pentru cel de-al treilea exemplu, putem selecta IP-urile (0, 1, 2), (1, 2, 0), (2, 0, 1).