시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB326527.778%

문제

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

각 플레이어는 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

예제 입력 2

3 14
1
1
1
1
1
2
3
4
5
6
8
9
9
9

예제 출력 2

2
W3sicHJvYmxlbV9pZCI6IjMxNDgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJlNTlcdWFjZTAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YmU1OVx1YWNlMCBcdWFjOGNcdWM3ODRcdWM1ZDBcdWMxMWMgXHVkNjM4XHVjMmE0XHVkMmI4XHViMjk0IFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWM3N2RcdWFjZTAsIFx1YWMwMSBcdWQ1MGNcdWI4MDhcdWM3NzRcdWM1YjRcdWIyOTQgXHVjNzkwXHVjMmUwXHVjNzU4IFx1YmU1OVx1YWNlMFx1ZDMxMFx1YzVkMFx1YzExYyBcdWFkZjggXHVjMjJiXHVjNzkwXHViOTdjIFx1Y2MzZVx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNFx1YjI5NCAxXHViZDgwXHVkMTMwIE48c3VwPjI8XC9zdXA+XHVhZTRjXHVjOWMwIFx1YzIyYlx1Yzc5MFx1YWMwMCBOXHVkNTg5IE5cdWM1ZjRcdWM1ZDAgXHVjODAxXHVkNjAwXHVjNzg4XHViMjk0IFx1ZDMxMFx1Yjk3YyBcdWI0ZTRcdWFjZTAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ2MzhcdWMyYTRcdWQyYjhcdWFjMDAgXHVjMjJiXHVjNzkwXHViOTdjIFx1Yzc3ZFx1YzczY1x1YmE3NCwgXHVkNTBjXHViODA4XHVjNzc0XHVjNWI0XHViMjk0IFx1ZDYzOFx1YzJhNFx1ZDJiOFx1YWMwMCBcdWJkODBcdWI5NzggXHVjZDVjXHVhZGZjIE5cdWFjMWNcdWM3NTggXHVjMjJiXHVjNzkwXHVhYzAwIFx1YmFhOFx1YjQ1MCBcdWM3ODhcdWIyOTQgXHVkNTg5XHVjNzc0IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWNjM2VcdWIyOTRcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHVhZGY4IFx1ZDU4OVx1YzVkMCBcdWM0ZjBcdWM1ZWMgXHVjNzg4XHViMjk0IFx1YzIyYlx1Yzc5MFx1Yzc1OCBcdWMyMWNcdWMxMWNcdWFjMDAgXHVkNjM4XHVjMmE0XHVkMmI4XHVhYzAwIFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWJkODBcdWI5NzggXHVjMjFjXHVjMTFjXHVhYzAwIFx1YWMxOVx1YzU0NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YjdmMCBcdWQ1ODlcdWM3NDQgXHVjYzNlXHVjNzQ0XHViNTRjXHViOWM4XHViMmU0IFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNFx1YjI5NCAxXHVjODEwXHVjNzQ0IFx1YzViYlx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgTlx1Yzc3NCAzXHVjNzdjXHViNTRjLCBcdWQ1MGNcdWI4MDhcdWM3NzRcdWM1YjRcdWFjMDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWJlNTlcdWFjZTBcdWQzMTBcdWM3NDQgXHViNGU0XHVhY2UwXHVjNzg4XHViMmU0XHVhY2UwIFx1YzBkZFx1YWMwMVx1ZDU3NFx1YmNmNFx1Yzc5MC48XC9wPlxyXG5cclxuPHRhYmxlIGNsYXNzPVwidGFibGUgdGFibGUtYm9yZGVyZWRcIiBzdHlsZT1cIndpZHRoOjklO1wiPlxyXG5cdDx0Ym9keT5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkIHN0eWxlPVwid2lkdGg6MyU7XCI+MTxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ3aWR0aDozJTtcIj4zPFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cIndpZHRoOjMlO1wiPjc8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+NjxcL3RkPlxyXG5cdFx0XHQ8dGQ+NDxcL3RkPlxyXG5cdFx0XHQ8dGQ+NTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD4yPFwvdGQ+XHJcblx0XHRcdDx0ZD44PFwvdGQ+XHJcblx0XHRcdDx0ZD45PFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90Ym9keT5cclxuPFwvdGFibGU+XHJcblxyXG48cD5cdWIzZDlcdWQ2MDFcdWM3NzRcdWIyOTQgXHViOWU0XHVjNzdjIFx1YmU1OVx1YWNlMFx1YWM4Y1x1Yzc4NFx1YzVkMFx1YzExYyBcdWFmMzRcdWI0ZjFcdWM3NDQgXHVkNTVjXHViMmU0LiBcdWM2MjRcdWIyOThcdWI5Y2NcdWM3NDAgXHVjNzdjXHViNGYxXHVjNzQ0IFx1ZDU1OFx1YWNhMFx1YjJlNFx1YWNlMCBcdWIyZTRcdWM5ZDBcdWQ1NWMgXHViM2Q5XHVkNjAxXHVjNzc0XHViMjk0IFx1ZDYzOFx1YzJhNFx1ZDJiOFx1YWMwMCBcdWJkODBcdWI5N2MgXHVjMjJiXHVjNzkwXHVjNzU4IFx1YzIxY1x1YzExY1x1YWMwMCBcdWM4MDFcdWQ2MDBcdWM3ODhcdWIyOTQgXHVjODg1XHVjNzc0XHViOTdjIFx1ZDZkNFx1Y2NkMFx1YzY1NFx1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWJlNTlcdWFjZTBcdWQzMTBcdWM3NTggXHVjMjJiXHVjNzkwXHViOTdjIFx1YzgwMVx1YzgwOFx1ZDc4OCBcdWJjMzBcdWNlNThcdWQ1ODhcdWM3NDQgXHViNTRjLCBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNkNWNcdWIzMDAgXHVjODEwXHVjMjE4XHViMjk0IFx1YmE4N1x1Yzc3OFx1YzljMFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViZTU5XHVhY2UwXHVkMzEwXHVjNzU4IFx1ZDA2Y1x1YWUzMCBOXHVhY2ZjIFx1ZDYzOFx1YzJhNFx1ZDJiOFx1YWMwMCBcdWJkODBcdWI5N2MgXHVjMjJiXHVjNzkwXHVjNzU4IFx1YWMxY1x1YzIxOCBCXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDIgJmxlOyBOICZsZTsgNCwgMSAmbGU7IEIgJmxlOyAxMDAwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIEJcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDYzOFx1YzJhNFx1ZDJiOFx1YWMwMCBcdWM3N2RcdWIyOTQgXHVjMjJiXHVjNzkwXHVhYzAwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWMyMmJcdWM3OTBcdWIyOTQgMVx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVhY2UwLCBOPHN1cD4yPFwvc3VwPlx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZDVjXHViMzAwIFx1YzgxMFx1YzIxOFx1YjI5NCBcdWJhODcgXHVjODEwXHVjNzc4XHVjOWMwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIzMTQ4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQklOR08iLCJkZXNjcmlwdGlvbiI6IjxwPkluIGEgc2ltcGxpZmllZCB2ZXJzaW9uIG9mIHRoZSBwb3B1bGFyIGdhbWUgb2YgQmluZ28sIHRoZSBob3N0IHJlYWRzIG51bWJlcnMgYW5kIGVhY2ggcGxheWVyIGxvb2tzIGZvciB0aG9zZSBudW1iZXJzIG9uIGhpcyBjYXJkLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIHBsYXllciBoYXMgYSBjYXJkIHdoaWNoIGNvbnRhaW5zIGFsbCB0aGUgbnVtYmVycyBmcm9tIDEgdG8gTjxzdXA+MjxcL3N1cD4gaW4gTiByb3dzIGFuZCBOIGNvbHVtbnMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBob3N0IHJlYWRzIHRoZSBudW1iZXJzIGFuZCB0aGUgcGxheWVycyBjaGVjayBpZiB0aGUgbGFzdCBOIG51bWJlcnMgcmVhZCBtYXRjaCBvbmUgb2YgdGhlIHJvd3Mgb24gdGhlaXIgY2FyZC4gTnVtYmVycyBvbiB0aGUgY2FyZCBoYXZlIHRvIGJlIGluIHRoZSBzYW1lIG9yZGVyIGFzIHRoZSByZWFkIG51bWJlcnMuIFRoZSBwbGF5ZXIgZ2V0cyAxcG9pbnQgZm9yIGVhY2ggbWF0Y2guJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCBzdXBwb3NlIE4gaXMgMyBhbmQgdGhlIHBsYXllciBoYXMgdGhlIGZvbGxvd2luZyBjYXJkOiZuYnNwOzxcL3A+XHJcblxyXG48dGFibGUgY2xhc3M9XCJ0YWJsZSB0YWJsZS1ib3JkZXJlZFwiIHN0eWxlPVwid2lkdGg6OSU7XCI+XHJcblx0PHRib2R5PlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ3aWR0aDozJTtcIj4xPFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cIndpZHRoOjMlO1wiPjM8XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwid2lkdGg6MyU7XCI+NzxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD42PFwvdGQ+XHJcblx0XHRcdDx0ZD40PFwvdGQ+XHJcblx0XHRcdDx0ZD41PFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjI8XC90ZD5cclxuXHRcdFx0PHRkPjg8XC90ZD5cclxuXHRcdFx0PHRkPjk8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3Rib2R5PlxyXG48XC90YWJsZT5cclxuXHJcbjxwPklmIHRoZSBob3N0IHJlYWRzIHRoZSBmb2xsb3dpbmcgbnVtYmVyczogNywgMSwgMywgNiwgNCwgNSwgNywgMSwgMiwgMiwgOCwgOSwgMywgdGhlbiB0aGUgcGxheWVyIGdldHMgMiBwb2ludHMsIGJlY2F1c2Ugc2VxdWVuY2VzIDYsIDQsIDUgYW5kIDIsIDgsIDkgYXBwZWFyIGFzIHJvd3Mgb24gaGlzIGNhcmQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkRpc2FwcG9pbnRlZCB3aXRoIGhpcyBjYXJkIGZvciB3aGljaCBoZSBnb3QgYSBzbWFsbCBudW1iZXIgb2YgcG9pbnRzLCBNaXJrbyB3b25kZXJzIHdoYXQgaXMgdGhlIGxhcmdlc3QgcG9zc2libGUgbnVtYmVyIG9mIHBvaW50cyBoZSBjb3VsZCBnZXQgaWYgdGhlIHNhbWUgbnVtYmVycyBhcmUgcmVhZCwgY29uc2lkZXJpbmcgYWxsIHBvc3NpYmxlIGNhcmRzLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzIE4gYW5kIEIgKDIgJmxlOyBOICZsZTsgNCwgMSAmbGU7IEIgJmxlOyAxMCAwMDApLCB0aGUgc2l6ZSBvZiB0aGUgY2FyZCBhbmQgdGhlIG51bWJlciBvZiBudW1iZXJzIHdoaWNoIHRoZSBob3N0IHJlYWRzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgZm9sbG93aW5nIEIgbGluZXMgY29udGFpbiBudW1iZXJzIHdoaWNoIHRoZSBob3N0IGhhcyByZWFkLiBFYWNoIG9mIHRob3NlIG51bWJlcnMgd2lsbCBiZSBiZXR3ZWVuIDEgYW5kIE48c3VwPjI8XC9zdXA+LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgbGFyZ2VzdCBudW1iZXIgb2YgcG9pbnRzIG92ZXIgYWxsIHBvc3NpYmxlIGNhcmRzLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5DbGFyaWZpY2F0aW9uIGZvciBmaXJzdCBleGFtcGxlOiBvbmUgb2YgdGhvc2UgY2FyZHMgaGFzIDEgMiAoY29udHJpYnV0ZXMgNCBwb2ludHMpIGFuZCAzIDQgKDEgcG9pbnQpIGluIGl0cyByb3dzLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==