시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHJcblxyXG48cD5cclxuXHRcdWQ2MzhcdWMyYTRcdWQyYjhcdWFjMDAgXHVjMjJiXHVjNzkwXHViOTdjIFx1Yzc3ZFx1YzczY1x1YmE3NCwgXHVkNTBjXHViODA4XHVjNzc0XHVjNWI0XHViMjk0IFx1ZDYzOFx1YzJhNFx1ZDJiOFx1YWMwMCBcdWJkODBcdWI5NzggXHVjZDVjXHVhZGZjIE5cdWFjMWNcdWM3NTggXHVjMjJiXHVjNzkwXHVhYzAwIFx1YmFhOFx1YjQ1MCBcdWM3ODhcdWIyOTQgXHVkNTg5XHVjNzc0IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWNjM2VcdWIyOTRcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHVhZGY4IFx1ZDU4OVx1YzVkMCBcdWM0ZjBcdWM1ZWMgXHVjNzg4XHViMjk0IFx1YzIyYlx1Yzc5MFx1Yzc1OCBcdWMyMWNcdWMxMWNcdWFjMDAgXHVkNjM4XHVjMmE0XHVkMmI4XHVhYzAwIFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWJkODBcdWI5NzggXHVjMjFjXHVjMTFjXHVhYzAwIFx1YWMxOVx1YzU0NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YjdmMCBcdWQ1ODlcdWM3NDQgXHVjYzNlXHVjNzQ0XHViNTRjXHViOWM4XHViMmU0IFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNFx1YjI5NCAxXHVjODEwXHVjNzQ0IFx1YzViYlx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgTlx1Yzc3NCAzXHVjNzdjXHViNTRjLCBcdWQ1MGNcdWI4MDhcdWM3NzRcdWM1YjRcdWFjMDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWJlNTlcdWFjZTBcdWQzMTBcdWM3NDQgXHViNGU0XHVhY2UwXHVjNzg4XHViMmU0XHVhY2UwIFx1YzBkZFx1YWMwMVx1ZDU3NFx1YmNmNFx1Yzc5MC48XC9wPlxyXG5cclxuPHRhYmxlIGNsYXNzPVwidGFibGUgdGFibGUtYm9yZGVyZWRcIiBzdHlsZT1cIndpZHRoOjklO1wiPlxyXG5cdDx0Ym9keT5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkIHN0eWxlPVwid2lkdGg6MyU7XCI+XHJcblx0XHRcdFx0MTxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ3aWR0aDozJTtcIj5cclxuXHRcdFx0XHQzPFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cIndpZHRoOjMlO1wiPlxyXG5cdFx0XHRcdDc8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+XHJcblx0XHRcdFx0NjxcL3RkPlxyXG5cdFx0XHQ8dGQ+XHJcblx0XHRcdFx0NDxcL3RkPlxyXG5cdFx0XHQ8dGQ+XHJcblx0XHRcdFx0NTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD5cclxuXHRcdFx0XHQyPFwvdGQ+XHJcblx0XHRcdDx0ZD5cclxuXHRcdFx0XHQ4PFwvdGQ+XHJcblx0XHRcdDx0ZD5cclxuXHRcdFx0XHQ5PFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90Ym9keT5cclxuPFwvdGFibGU+XHJcblxyXG48cD5cclxuXHRcdWIzZDlcdWQ2MDFcdWM3NzRcdWIyOTQgXHViOWU0XHVjNzdjIFx1YmU1OVx1YWNlMFx1YWM4Y1x1Yzc4NFx1YzVkMFx1YzExYyBcdWFmMzRcdWI0ZjFcdWM3NDQgXHVkNTVjXHViMmU0LiBcdWM2MjRcdWIyOThcdWI5Y2NcdWM3NDAgXHVjNzdjXHViNGYxXHVjNzQ0IFx1ZDU1OFx1YWNhMFx1YjJlNFx1YWNlMCBcdWIyZTRcdWM5ZDBcdWQ1NWMgXHViM2Q5XHVkNjAxXHVjNzc0XHViMjk0IFx1ZDYzOFx1YzJhNFx1ZDJiOFx1YWMwMCBcdWJkODBcdWI5N2MgXHVjMjJiXHVjNzkwXHVjNzU4IFx1YzIxY1x1YzExY1x1YWMwMCBcdWM4MDFcdWQ2MDBcdWM3ODhcdWIyOTQgXHVjODg1XHVjNzc0XHViOTdjIFx1ZDZkNFx1Y2NkMFx1YzY1NFx1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWJlNTlcdWFjZTBcdWQzMTBcdWM3NTggXHVjMjJiXHVjNzkwXHViOTdjIFx1YzgwMVx1YzgwOFx1ZDc4OCBcdWJjMzBcdWNlNThcdWQ1ODhcdWM3NDQgXHViNTRjLCBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNkNWNcdWIzMDAgXHVjODEwXHVjMjE4XHViMjk0IFx1YmE4N1x1Yzc3OFx1YzljMFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViZTU5XHVhY2UwXHVkMzEwXHVjNzU4IFx1ZDA2Y1x1YWUzMCBOXHVhY2ZjIFx1ZDYzOFx1YzJhNFx1ZDJiOFx1YWMwMCBcdWJkODBcdWI5N2MgXHVjMjJiXHVjNzkwXHVjNzU4IFx1YWMxY1x1YzIxOCBCXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDIgJmxlOyBOICZsZTsgNCwgMSAmbGU7IEIgJmxlOyAxMDAwMCk8XC9wPlxyXG5cclxuPHA+XHJcblx0XHViMmU0XHVjNzRjIEJcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDYzOFx1YzJhNFx1ZDJiOFx1YWMwMCBcdWM3N2RcdWIyOTQgXHVjMjJiXHVjNzkwXHVhYzAwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWMyMmJcdWM3OTBcdWIyOTQgMVx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVhY2UwLCBOPHN1cD4yPFwvc3VwPlx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZDVjXHViMzAwIFx1YzgxMFx1YzIxOFx1YjI5NCBcdWJhODcgXHVjODEwXHVjNzc4XHVjOWMwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMTQ4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQklOR08iLCJkZXNjcmlwdGlvbiI6IjxwPkluIGEgc2ltcGxpZmllZCB2ZXJzaW9uIG9mIHRoZSBwb3B1bGFyIGdhbWUgb2YgQmluZ28sIHRoZSBob3N0IHJlYWRzIG51bWJlcnMgYW5kIGVhY2ggcGxheWVyIGxvb2tzIGZvciB0aG9zZSBudW1iZXJzIG9uIGhpcyBjYXJkLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIHBsYXllciBoYXMgYSBjYXJkIHdoaWNoIGNvbnRhaW5zIGFsbCB0aGUgbnVtYmVycyBmcm9tIDEgdG8gTjxzdXA+MjxcL3N1cD4gaW4gTiByb3dzIGFuZCBOIGNvbHVtbnMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBob3N0IHJlYWRzIHRoZSBudW1iZXJzIGFuZCB0aGUgcGxheWVycyBjaGVjayBpZiB0aGUgbGFzdCBOIG51bWJlcnMgcmVhZCBtYXRjaCBvbmUgb2YgdGhlIHJvd3Mgb24gdGhlaXIgY2FyZC4gTnVtYmVycyBvbiB0aGUgY2FyZCBoYXZlIHRvIGJlIGluIHRoZSBzYW1lIG9yZGVyIGFzIHRoZSByZWFkIG51bWJlcnMuIFRoZSBwbGF5ZXIgZ2V0cyAxcG9pbnQgZm9yIGVhY2ggbWF0Y2guJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCBzdXBwb3NlIE4gaXMgMyBhbmQgdGhlIHBsYXllciBoYXMgdGhlIGZvbGxvd2luZyBjYXJkOiZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2JpbmdvLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEzNXB4OyB3aWR0aDoxMjlweFwiIFwvPjxcL3A+XHJcblxyXG48cD5JZiB0aGUgaG9zdCByZWFkcyB0aGUgZm9sbG93aW5nIG51bWJlcnM6IDcsIDEsIDMsIDYsIDQsIDUsIDcsIDEsIDIsIDIsIDgsIDksIDMsIHRoZW4gdGhlIHBsYXllciBnZXRzIDIgcG9pbnRzLCBiZWNhdXNlIHNlcXVlbmNlcyA2LCA0LCA1IGFuZCAyLCA4LCA5IGFwcGVhciBhcyByb3dzIG9uIGhpcyBjYXJkLiZuYnNwOzxcL3A+XHJcblxyXG48cD5EaXNhcHBvaW50ZWQgd2l0aCBoaXMgY2FyZCBmb3Igd2hpY2ggaGUgZ290IGEgc21hbGwgbnVtYmVyIG9mIHBvaW50cywgTWlya28gd29uZGVycyB3aGF0IGlzIHRoZSBsYXJnZXN0IHBvc3NpYmxlIG51bWJlciBvZiBwb2ludHMgaGUgY291bGQgZ2V0IGlmIHRoZSBzYW1lIG51bWJlcnMgYXJlIHJlYWQsIGNvbnNpZGVyaW5nIGFsbCBwb3NzaWJsZSBjYXJkcy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBOIGFuZCBCICgyICZsZTsgTiAmbGU7IDQsIDEgJmxlOyBCICZsZTsgMTAgMDAwKSwgdGhlIHNpemUgb2YgdGhlIGNhcmQgYW5kIHRoZSBudW1iZXIgb2YgbnVtYmVycyB3aGljaCB0aGUgaG9zdCByZWFkcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGZvbGxvd2luZyBCIGxpbmVzIGNvbnRhaW4gbnVtYmVycyB3aGljaCB0aGUgaG9zdCBoYXMgcmVhZC4gRWFjaCBvZiB0aG9zZSBudW1iZXJzIHdpbGwgYmUgYmV0d2VlbiAxIGFuZCBOPHN1cD4yPFwvc3VwPi4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIGxhcmdlc3QgbnVtYmVyIG9mIHBvaW50cyBvdmVyIGFsbCBwb3NzaWJsZSBjYXJkcy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=