시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 2 1 1 100.000%

문제

빙고 게임에서 호스트는 숫자를 읽고, 각 플레이어는 자신의 빙고판에서 그 숫자를 찾는다.

각 플레이어는 1부터 N2까지 숫자가 N행 N열에 적혀있는 판를 들고 있다.

호스트가 숫자를 읽으면, 플레이어는 호스트가 부른 최근 N개의 숫자가 모두 있는 행이 있는지 찾는다. 이 때, 그 행에 써있는 숫자의 순서가 호스트가 숫자를 부른 순서가 같아야 한다. 이런 행을 찾을때마다 플레이어는 1점을 얻는다.

예를 들어, N이 3일때, 플레이어가 다음과 같은 빙고판을 들고있다고 생각해보자.

1 3 7
6 4 5
2 8 9

동혁이는 매일 빙고게임에서 꼴등을 한다. 오늘만은 일등을 하겠다고 다짐한 동혁이는 호스트가 부를 숫자의 순서가 적혀있는 종이를 훔쳐왔다. 이 때, 빙고판의 숫자를 적절히 배치했을 때, 얻을 수 있는 최대 점수는 몇인지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 빙고판의 크기 N과 호스트가 부를 숫자의 개수 B가 주어진다. (2 ≤ N ≤ 4, 1 ≤ B ≤ 10000)

다음 B개 줄에는 호스트가 읽는 숫자가 순서대로 주어진다. 모든 숫자는 1보다 크거나 같고, N2보다 작거나 같다.

출력

첫째 줄에 얻을 수 있는 최대 점수는 몇 점인지 출력한다.

예제 입력 1

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

예제 출력 1

5
W3sicHJvYmxlbV9pZCI6IjMxNDgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJlNTlcdWFjZTAiLCJkZXNjcmlwdGlvbiI6IjxwPlxyXG5cdFx1YmU1OVx1YWNlMCBcdWFjOGNcdWM3ODRcdWM1ZDBcdWMxMWMgXHVkNjM4XHVjMmE0XHVkMmI4XHViMjk0IFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWM3N2RcdWFjZTAsIFx1YWMwMSBcdWQ1MGNcdWI4MDhcdWM3NzRcdWM1YjRcdWIyOTQgXHVjNzkwXHVjMmUwXHVjNzU4IFx1YmU1OVx1YWNlMFx1ZDMxMFx1YzVkMFx1YzExYyBcdWFkZjggXHVjMjJiXHVjNzkwXHViOTdjIFx1Y2MzZVx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVhYzAxIFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNFx1YjI5NCAxXHViZDgwXHVkMTMwIE48c3VwPjI8XC9zdXA+XHVhZTRjXHVjOWMwIFx1YzIyYlx1Yzc5MFx1YWMwMCBOXHVkNTg5IE5cdWM1ZjRcdWM1ZDAgXHVjODAxXHVkNjAwXHVjNzg4XHViMjk0IFx1ZDMxMFx1Yjk3YyBcdWI0ZTRcdWFjZTAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWQ2MzhcdWMyYTRcdWQyYjhcdWFjMDAgXHVjMjJiXHVjNzkwXHViOTdjIFx1Yzc3ZFx1YzczY1x1YmE3NCwgXHVkNTBjXHViODA4XHVjNzc0XHVjNWI0XHViMjk0IFx1ZDYzOFx1YzJhNFx1ZDJiOFx1YWMwMCBcdWJkODBcdWI5NzggXHVjZDVjXHVhZGZjIE5cdWFjMWNcdWM3NTggXHVjMjJiXHVjNzkwXHVhYzAwIFx1YmFhOFx1YjQ1MCBcdWM3ODhcdWIyOTQgXHVkNTg5XHVjNzc0IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWNjM2VcdWIyOTRcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIFx1YWRmOCBcdWQ1ODlcdWM1ZDAgXHVjMzY4XHVjNzg4XHViMjk0IFx1YzIyYlx1Yzc5MFx1Yzc1OCBcdWMyMWNcdWMxMWNcdWFjMDAgXHVkNjM4XHVjMmE0XHVkMmI4XHVhYzAwIFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWJkODBcdWI5NzggXHVjMjFjXHVjMTFjXHVhYzAwIFx1YWMxOVx1YzU0NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YjdmMCBcdWQ1ODlcdWM3NDQgXHVjYzNlXHVjNzQ0XHViNTRjXHViOWM4XHViMmU0IFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNFx1YjI5NCAxXHVjODEwXHVjNzQ0IFx1YzViYlx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgTlx1Yzc3NCAzXHVjNzdjXHViNTRjLCBcdWQ1MGNcdWI4MDhcdWM3NzRcdWM1YjRcdWFjMDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWJlNTlcdWFjZTBcdWQzMTBcdWM3NDQgXHViNGU0XHVhY2UwXHVjNzg4XHViMmU0XHVhY2UwIFx1YzBkZFx1YWMwMVx1ZDU3NFx1YmNmNFx1Yzc5MC48XC9wPlxyXG5cclxuPHRhYmxlIGNsYXNzPVwidGFibGUgdGFibGUtYm9yZGVyZWRcIiBzdHlsZT1cIndpZHRoOjklO1wiPlxyXG5cdDx0Ym9keT5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkIHN0eWxlPVwid2lkdGg6MyU7XCI+XHJcblx0XHRcdFx0MTxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ3aWR0aDozJTtcIj5cclxuXHRcdFx0XHQzPFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cIndpZHRoOjMlO1wiPlxyXG5cdFx0XHRcdDc8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+XHJcblx0XHRcdFx0NjxcL3RkPlxyXG5cdFx0XHQ8dGQ+XHJcblx0XHRcdFx0NDxcL3RkPlxyXG5cdFx0XHQ8dGQ+XHJcblx0XHRcdFx0NTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD5cclxuXHRcdFx0XHQyPFwvdGQ+XHJcblx0XHRcdDx0ZD5cclxuXHRcdFx0XHQ4PFwvdGQ+XHJcblx0XHRcdDx0ZD5cclxuXHRcdFx0XHQ5PFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90Ym9keT5cclxuPFwvdGFibGU+XHJcblxyXG48cD5cclxuXHRcdWIzZDlcdWQ2MDFcdWM3NzRcdWIyOTQgXHViOWU0XHVjNzdjIFx1YmU1OVx1YWNlMFx1YWM4Y1x1Yzc4NFx1YzVkMFx1YzExYyBcdWFmMzRcdWI0ZjFcdWM3NDQgXHVkNTVjXHViMmU0LiBcdWM2MjRcdWIyOThcdWI5Y2NcdWM3NDAgXHVjNzdjXHViNGYxXHVjNzQ0IFx1ZDU1OFx1YWNhMFx1YjJlNFx1YWNlMCBcdWIyZTRcdWM5ZDBcdWQ1NWMgXHViM2Q5XHVkNjAxXHVjNzc0XHViMjk0IFx1ZDYzOFx1YzJhNFx1ZDJiOFx1YWMwMCBcdWJkODBcdWI5N2MgXHVjMjJiXHVjNzkwXHVjNzU4IFx1YzIxY1x1YzExY1x1YWMwMCBcdWM4MDFcdWQ2MDBcdWM3ODhcdWIyOTQgXHVjODg1XHVjNzc0XHViOTdjIFx1ZDZkNFx1Y2NkMFx1YzY1NFx1YjJlNC4gXHVjNzc0IFx1YjU0YywgXHViZTU5XHVhY2UwXHVkMzEwXHVjNzU4IFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWM4MDFcdWM4MDhcdWQ3ODggXHViYzMwXHVjZTU4XHVkNTg4XHVjNzQ0IFx1YjU0YywgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZDVjXHViMzAwIFx1YzgxMFx1YzIxOFx1YjI5NCBcdWJhODdcdWM3NzhcdWM5YzBcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmU1OVx1YWNlMFx1ZDMxMFx1Yzc1OCBcdWQwNmNcdWFlMzAgTlx1YWNmYyBcdWQ2MzhcdWMyYTRcdWQyYjhcdWFjMDAgXHViZDgwXHViOTdjIFx1YzIyYlx1Yzc5MFx1Yzc1OCBcdWFjMWNcdWMyMTggQlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgyICZsZTsgTiAmbGU7IDQsIDEgJmxlOyBCICZsZTsgMTAwMDApPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjJlNFx1Yzc0YyBCXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQ2MzhcdWMyYTRcdWQyYjhcdWFjMDAgXHVjNzdkXHViMjk0IFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWJhYThcdWI0ZTAgXHVjMjJiXHVjNzkwXHViMjk0IDFcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YWNlMCwgTjxzdXA+MjxcL3N1cD5cdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2Q1Y1x1YjMwMCBcdWM4MTBcdWMyMThcdWIyOTQgXHViYTg3IFx1YzgxMFx1Yzc3OFx1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzE0OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJJTkdPIiwiZGVzY3JpcHRpb24iOiI8cD5JbiBhIHNpbXBsaWZpZWQgdmVyc2lvbiBvZiB0aGUgcG9wdWxhciBnYW1lIG9mIEJpbmdvLCB0aGUgaG9zdCByZWFkcyBudW1iZXJzIGFuZCBlYWNoIHBsYXllciBsb29rcyBmb3IgdGhvc2UgbnVtYmVycyBvbiBoaXMgY2FyZC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBwbGF5ZXIgaGFzIGEgY2FyZCB3aGljaCBjb250YWlucyBhbGwgdGhlIG51bWJlcnMgZnJvbSAxIHRvIE48c3VwPjI8XC9zdXA+IGluIE4gcm93cyBhbmQgTiBjb2x1bW5zLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgaG9zdCByZWFkcyB0aGUgbnVtYmVycyBhbmQgdGhlIHBsYXllcnMgY2hlY2sgaWYgdGhlIGxhc3QgTiBudW1iZXJzIHJlYWQgbWF0Y2ggb25lIG9mIHRoZSByb3dzIG9uIHRoZWlyIGNhcmQuIE51bWJlcnMgb24gdGhlIGNhcmQgaGF2ZSB0byBiZSBpbiB0aGUgc2FtZSBvcmRlciBhcyB0aGUgcmVhZCBudW1iZXJzLiBUaGUgcGxheWVyIGdldHMgMXBvaW50IGZvciBlYWNoIG1hdGNoLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgc3VwcG9zZSBOIGlzIDMgYW5kIHRoZSBwbGF5ZXIgaGFzIHRoZSBmb2xsb3dpbmcgY2FyZDombmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9iaW5nby5wbmdcIiBzdHlsZT1cImhlaWdodDoxMzVweDsgd2lkdGg6MTI5cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+SWYgdGhlIGhvc3QgcmVhZHMgdGhlIGZvbGxvd2luZyBudW1iZXJzOiA3LCAxLCAzLCA2LCA0LCA1LCA3LCAxLCAyLCAyLCA4LCA5LCAzLCB0aGVuIHRoZSBwbGF5ZXIgZ2V0cyAyIHBvaW50cywgYmVjYXVzZSBzZXF1ZW5jZXMgNiwgNCwgNSBhbmQgMiwgOCwgOSBhcHBlYXIgYXMgcm93cyBvbiBoaXMgY2FyZC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RGlzYXBwb2ludGVkIHdpdGggaGlzIGNhcmQgZm9yIHdoaWNoIGhlIGdvdCBhIHNtYWxsIG51bWJlciBvZiBwb2ludHMsIE1pcmtvIHdvbmRlcnMgd2hhdCBpcyB0aGUgbGFyZ2VzdCBwb3NzaWJsZSBudW1iZXIgb2YgcG9pbnRzIGhlIGNvdWxkIGdldCBpZiB0aGUgc2FtZSBudW1iZXJzIGFyZSByZWFkLCBjb25zaWRlcmluZyBhbGwgcG9zc2libGUgY2FyZHMuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0d28gaW50ZWdlcnMgTiBhbmQgQiAoMiAmbGU7IE4gJmxlOyA0LCAxICZsZTsgQiAmbGU7IDEwIDAwMCksIHRoZSBzaXplIG9mIHRoZSBjYXJkIGFuZCB0aGUgbnVtYmVyIG9mIG51bWJlcnMgd2hpY2ggdGhlIGhvc3QgcmVhZHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBmb2xsb3dpbmcgQiBsaW5lcyBjb250YWluIG51bWJlcnMgd2hpY2ggdGhlIGhvc3QgaGFzIHJlYWQuIEVhY2ggb2YgdGhvc2UgbnVtYmVycyB3aWxsIGJlIGJldHdlZW4gMSBhbmQgTjxzdXA+MjxcL3N1cD4uJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSBsYXJnZXN0IG51bWJlciBvZiBwb2ludHMgb3ZlciBhbGwgcG9zc2libGUgY2FyZHMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d