Codah ClubTrain. Submit. Improve.
Sign in
English
#00043B

Bingo

In a simplified version of the popular game of Bingo, the host reads numbers and each player looks for those numbers on his card. Each player has a card which contains all the numbers from 1 to N2 in N rows and N columns. The host reads the numbers and the players check if the last N numbers read match one of the rows on their card. Numbers on the card have to be in the same order as the read numbers. The player gets 1 point for each match. For example, suppose N is 3 and the player has the following card:

Image: dsadsa
If the host reads the following numbers: 7, 1, 3, 6, 4, 5, 7, 1, 2, 2, 8, 9, 3, then the player gets 2 points, because sequences 6, 4, 5 and 2, 8, 9 appear as rows on his card. Disappointed with his card for which he got a small number of points, Mirko wonders what is the largest possible number of points he could get if the same numbers are read, considering all possible cards.


InputThe first line contains two integers N and B (2 ≤ N ≤ 4, 1 ≤ B ≤ 10 000), the size of the card and the number of numbers which the host reads. The following B lines contain numbers which the host has read. Each of those numbers will be between 1 and N^2.

OutputOutput the largest number of points over all possible cards.

Input
2 11
1
2
1
2
1
2
1
2
3
4
1
Output
5

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.