시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 256 MB 279 54 30 20.134%

문제

추석 연휴를 맞아 홍준이는 자신의 집에서 파티를 열었다. 파티에는 어린 아이들도 많이 왔다. 다음 날 홍준이는 자신의 침대에 여러 얼룩들이 있는 것을 보았다. 그 얼룩들은 침대 시트 밑의 매트릭스까지 스며들었다. 매트릭스 전체를 청소하는 비용이 매우 비싼 관계로 홍준이는 작은 매트릭스 청소 도구를 구매하려한다.

매트릭스의 윗 면은 M × N 크기의 직사각형 격자로 볼 수 있다. 즉, 매트릭스의 수직 성분 개수는 M 개이며 수평 선분 개수는 N 개다. 매트릭스의 각 격자를 좌표로 나타낼 수 있는데, 매트릭스의 왼쪽-위 격자의 좌표는 (1, 1)이며, 오른쪽-아래 격자의 좌표는 (m, n)이다. 한 얼룩은 격자 하나를 덮는다.

홍준이가 구매하려는 매트릭스 청소 도구는 연속하고 직사각형 변에 평행한 3 × 3 영역에 있는 모든 얼룩을 지워주는 도구다. 도구는 하나 사면 한 번만 얼룩을 지울 수 있는 소비성이 있는 도구다. 홍준이를 위해 매트릭스 크기와 얼룩에 대한 정보가 주어졌을 때, 필요한 청소 도구의 최소 개수를 구하자.

<그림 1>은 가능한 상황의 한 예다. 매트릭스의 크기는 6 × 11이며, 각 얼룩의 위치 좌표는 (4, 3), (6, 5), (3, 6)과 (4,7)이다. 위와 같은 경우에 필요한 청소 도구의 최소 개수는 2개다.

입력

입력은 여러 개의 테스트케이스로 구성되어 있다.

각 테스트케이스의 첫 줄에는 매트릭스의 크기를 나타내는 두 자연수 m과 n이 주어진다. (3 ≤ m ≤ 10, 3 ≤ n ≤ 1,000). 둘째 줄에는 얼룩의 개수를 나타내는 정수 c가 주어진다. (0 ≤ c ≤ mn) 그리고 다음 c개의 줄에 각 얼룩의 좌표가 주어진다. 얼룩의 좌표는 서로 다르게 주어지며, 모두 매트릭스 위에 위치한다.

출력

각 테스트케이스 별로 얼룩을 모두 지우기 위해 필요한 청소 도구의 최소 개수를 의미하는 하나의 정수를 출력한다.

예제 입력 1

2
6 11
4
4 3
6 5 
3 6
4 7 
7 7
4 
3 2
5 6
6 4
7 6

예제 출력 1

2
2

힌트

W3sicHJvYmxlbV9pZCI6IjEwMjU3IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjNWJjXHViOGU5IiwiZGVzY3JpcHRpb24iOiI8cD5cdWNkOTRcdWMxMWQgXHVjNWYwXHVkNzM0XHViOTdjIFx1YjlkZVx1YzU0NCBcdWQ2NGRcdWM5MDBcdWM3NzRcdWIyOTQgXHVjNzkwXHVjMmUwXHVjNzU4IFx1YzlkMVx1YzVkMFx1YzExYyBcdWQzMGNcdWQyZjBcdWI5N2MgXHVjNWY0XHVjNWM4XHViMmU0LiBcdWQzMGNcdWQyZjBcdWM1ZDBcdWIyOTQgXHVjNWI0XHViOWIwIFx1YzU0NFx1Yzc3NFx1YjRlNFx1YjNjNCBcdWI5Y2VcdWM3NzQgXHVjNjU0XHViMmU0LiBcdWIyZTRcdWM3NGMgXHViMGEwIFx1ZDY0ZFx1YzkwMFx1Yzc3NFx1YjI5NCBcdWM3OTBcdWMyZTBcdWM3NTggXHVjZTY4XHViMzAwXHVjNWQwIFx1YzVlY1x1YjdlYyBcdWM1YmNcdWI4ZTlcdWI0ZTRcdWM3NzQgXHVjNzg4XHViMjk0IFx1YWM4M1x1Yzc0NCBcdWJjZjRcdWM1NThcdWIyZTQuIFx1YWRmOCBcdWM1YmNcdWI4ZTlcdWI0ZTRcdWM3NDAgXHVjZTY4XHViMzAwIFx1YzJkY1x1ZDJiOCBcdWJjMTFcdWM3NTggXHViOWU0XHVkMmI4XHViOWFkXHVjMmE0XHVhZTRjXHVjOWMwIFx1YzJhNFx1YmE3MFx1YjRlNFx1YzVjOFx1YjJlNC4gXHViOWU0XHVkMmI4XHViOWFkXHVjMmE0IFx1YzgwNFx1Y2NiNFx1Yjk3YyBcdWNjYWRcdWMxOGNcdWQ1NThcdWIyOTQgXHViZTQ0XHVjNmE5XHVjNzc0IFx1YjllNFx1YzZiMCBcdWJlNDRcdWMyZmMgXHVhZDAwXHVhY2M0XHViODVjIFx1ZDY0ZFx1YzkwMFx1Yzc3NFx1YjI5NCBcdWM3OTFcdWM3NDAgXHViOWU0XHVkMmI4XHViOWFkXHVjMmE0IFx1Y2NhZFx1YzE4YyBcdWIzYzRcdWFkNmNcdWI5N2MgXHVhZDZjXHViOWU0XHVkNTU4XHViODI0XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXMyXC9zdGFpbnMucG5nXCIgc3R5bGU9XCJmbG9hdDpyaWdodDsgbWFyZ2luOjBweCAwcHggMTBweCAxMHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YjllNFx1ZDJiOFx1YjlhZFx1YzJhNFx1Yzc1OCBcdWM3MTcgXHViYTc0XHVjNzQwIE0gJnRpbWVzOyBOIFx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTUgXHVhY2E5XHVjNzkwXHViODVjIFx1YmNmYyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM5ODksIFx1YjllNFx1ZDJiOFx1YjlhZFx1YzJhNFx1Yzc1OCBcdWMyMThcdWM5YzEgXHVjMTMxXHViZDg0IFx1YWMxY1x1YzIxOFx1YjI5NCBNIFx1YWMxY1x1Yzc3NFx1YmE3MCBcdWMyMThcdWQzYzkgXHVjMTIwXHViZDg0IFx1YWMxY1x1YzIxOFx1YjI5NCBOIFx1YWMxY1x1YjJlNC4gXHViOWU0XHVkMmI4XHViOWFkXHVjMmE0XHVjNzU4IFx1YWMwMSBcdWFjYTlcdWM3OTBcdWI5N2MgXHVjODhjXHVkNDVjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMjk0XHViMzcwLCBcdWI5ZTRcdWQyYjhcdWI5YWRcdWMyYTRcdWM3NTggXHVjNjdjXHVjYWJkLVx1YzcwNCBcdWFjYTlcdWM3OTBcdWM3NTggXHVjODhjXHVkNDVjXHViMjk0ICgxLCAxKVx1Yzc3NFx1YmE3MCwgXHVjNjI0XHViOTc4XHVjYWJkLVx1YzU0NFx1Yjc5OCBcdWFjYTlcdWM3OTBcdWM3NTggXHVjODhjXHVkNDVjXHViMjk0IChtLCBuKVx1Yzc3NFx1YjJlNC4gXHVkNTVjIFx1YzViY1x1YjhlOVx1Yzc0MCBcdWFjYTlcdWM3OTAgXHVkNTU4XHViMDk4XHViOTdjIFx1YjM2ZVx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNjRkXHVjOTAwXHVjNzc0XHVhYzAwIFx1YWQ2Y1x1YjllNFx1ZDU1OFx1YjgyNFx1YjI5NCBcdWI5ZTRcdWQyYjhcdWI5YWRcdWMyYTQgXHVjY2FkXHVjMThjIFx1YjNjNFx1YWQ2Y1x1YjI5NCBcdWM1ZjBcdWMxOGRcdWQ1NThcdWFjZTAgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1IFx1YmNjMFx1YzVkMCBcdWQzYzlcdWQ1ODlcdWQ1NWMgMyAmdGltZXM7IDMgXHVjNjAxXHVjNWVkXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVjNWJjXHViOGU5XHVjNzQ0IFx1YzljMFx1YzZjY1x1YzhmY1x1YjI5NCBcdWIzYzRcdWFkNmNcdWIyZTQuIFx1YjNjNFx1YWQ2Y1x1YjI5NCBcdWQ1NThcdWIwOTggXHVjMGFjXHViYTc0IFx1ZDU1YyBcdWJjODhcdWI5Y2MgXHVjNWJjXHViOGU5XHVjNzQ0IFx1YzljMFx1YzZiOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzE4Y1x1YmU0NFx1YzEzMVx1Yzc3NCBcdWM3ODhcdWIyOTQgXHViM2M0XHVhZDZjXHViMmU0LiBcdWQ2NGRcdWM5MDBcdWM3NzRcdWI5N2MgXHVjNzA0XHVkNTc0IFx1YjllNFx1ZDJiOFx1YjlhZFx1YzJhNCBcdWQwNmNcdWFlMzBcdWM2NDAgXHVjNWJjXHViOGU5XHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1Y2NhZFx1YzE4YyBcdWIzYzRcdWFkNmNcdWM3NTggXHVjZDVjXHVjMThjIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWM3OTAuPFwvcD5cclxuXHJcbjxwPiZsdDtcdWFkZjhcdWI5YmMgMSZndDtcdWM3NDAgXHVhYzAwXHViMmE1XHVkNTVjIFx1YzBjMVx1ZDY2OVx1Yzc1OCBcdWQ1NWMgXHVjNjA4XHViMmU0LiBcdWI5ZTRcdWQyYjhcdWI5YWRcdWMyYTRcdWM3NTggXHVkMDZjXHVhZTMwXHViMjk0IDYgJnRpbWVzOyAxMVx1Yzc3NFx1YmE3MCwgXHVhYzAxIFx1YzViY1x1YjhlOVx1Yzc1OCBcdWM3MDRcdWNlNTggXHVjODhjXHVkNDVjXHViMjk0ICg0LCAzKSwgKDYsIDUpLCAoMywgNilcdWFjZmMgKDQsNylcdWM3NzRcdWIyZTQuIFx1YzcwNFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVhY2JkXHVjNmIwXHVjNWQwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWNjYWRcdWMxOGMgXHViM2M0XHVhZDZjXHVjNzU4IFx1Y2Q1Y1x1YzE4YyBcdWFjMWNcdWMyMThcdWIyOTQgMlx1YWMxY1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWFkNmNcdWMxMzFcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4XHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYiBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViOWU0XHVkMmI4XHViOWFkXHVjMmE0XHVjNzU4IFx1ZDA2Y1x1YWUzMFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHViNDUwIFx1Yzc5MFx1YzVmMFx1YzIxOCBtXHVhY2ZjIG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMyAmbGU7IG0gJmxlOyAxMCwgMyAmbGU7IG4gJmxlOyAxLDAwMCkuJm5ic3A7XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM1YmNcdWI4ZTlcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWM4MTVcdWMyMTggY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgwICZsZTsgYyAmbGU7IG1uKSZuYnNwO1x1YWRmOFx1YjlhY1x1YWNlMCBcdWIyZTRcdWM3NGMgY1x1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzAxIFx1YzViY1x1YjhlOVx1Yzc1OCBcdWM4OGNcdWQ0NWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM1YmNcdWI4ZTlcdWM3NTggXHVjODhjXHVkNDVjXHViMjk0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzRcdWFjOGMgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCBcdWJhYThcdWI0NTAgXHViOWU0XHVkMmI4XHViOWFkXHVjMmE0IFx1YzcwNFx1YzVkMCBcdWM3MDRcdWNlNThcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1Y2YwMFx1Yzc3NFx1YzJhNCBcdWJjYzRcdWI4NWMgXHVjNWJjXHViOGU5XHVjNzQ0IFx1YmFhOFx1YjQ1MCBcdWM5YzBcdWM2YjBcdWFlMzAgXHVjNzA0XHVkNTc0IFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWNjYWRcdWMxOGMgXHViM2M0XHVhZDZjXHVjNzU4IFx1Y2Q1Y1x1YzE4YyBcdWFjMWNcdWMyMThcdWI5N2MgXHVjNzU4XHViYmY4XHVkNTU4XHViMjk0IFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWM4MTVcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjEwMjU3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU3RhaW5zIiwiZGVzY3JpcHRpb24iOiI8cD5EdXJpbmcgdGhlIENodVNlb2sgaG9saWRheXMgeW91IGhhZCBxdWl0ZSBhIGZldyBndWVzdHMsIGluY2x1ZGluZyBzb21lIHZlcnkgeW91bmcgYm95cy4gQWZ0ZXIgdGhleSB3ZW50IGJhY2sgdG8gdGhlaXIgcmVzcGVjdGl2ZSBob21lcywgeW91IGZvdW5kIHNvbWUgc3RhaW5zIG9uIHlvdXIgYmVkLiBUaGUgc3RhaW5zIGFyZSBkZWVwIGFuZCBhY3R1YWxseSBnbyBpbnRvIHRoZSBtYXR0cmVzcy4gSXQgaXMgcXVpdGUgZXhwZW5zaXZlIHRvIGNsZWFuIHRoZSB3aG9sZSBtYXR0cmVzcywgc28geW91IGhhdmUgZGVjaWRlZCB0byBidXkgYSBmZXcgb2YgdGhlIGNsZWFuLW1hdHRyZXNzLXNxdWFyZXMsIHdoaWNoIGNhbiBjbGVhbiBzb21lIGFyZWEgb2YgdGhlIG1hdHRyZXNzLiBUaGUgc3VyZmFjZSBvZiB0aGUgbWF0dHJlc3MgY2FuIGJlIGRpdmlkZWQgaW50byBhbiBtICZ0aW1lczsgbiBncmlkLCBpLmUuLCBhIHJlY3RhbmdsZSB3aXRoIG0gdW5pdCBzcXVhcmVzIHZlcnRpY2FsbHkgYW5kIG4gdW5pdCBzcXVhcmVzIGhvcml6b250YWxseS4gQSBjb29yZGluYXRlIHN5c3RlbSBpcyBkZWZpbmVkIHNvIHRoYXQgdGhlIHVuaXQgc3F1YXJlIGF0IHRoZSB0b3AtbGVmdCBjb3JuZXIgaGFzIGNvb3JkaW5hdGUgKDEsIDEpIGFuZCB0aGUgdW5pdCBzcXVhcmUgYXQgdGhlIGJvdHRvbS1yaWdodCBjb3JuZXIgaGFzIChtLCBuKS4gSW4gZWFjaCBzcXVhcmUgdGhlcmUgbWF5IGJlIGEgc3RhaW4uIEVhY2ggb2YgeW91ciBjbGVhbi1tYXR0cmVzcy1zcXVhcmVzIGlzIGFibGUgdG8gY2xlYW4gdXAgYWxsIHN0YWlucyBpbiBhIDMgJnRpbWVzOyAzIGFyZWEuIFlvdXIgbWlzc2lvbiBpcyB0byBtaW5pbWl6ZSB0aGUgbnVtYmVyIG9mIGNsZWFuLW1hdHRyZXNzLXNxdWFyZXMgdG8gYmUgdXNlZCB3aGlsZSwgb2YgY291cnNlLCByZW1vdmluZyBhbGwgb2YgdGhlIHN0YWlucy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzMlwvc3RhaW5zLnBuZ1wiIHN0eWxlPVwiZmxvYXQ6cmlnaHQ7IGhlaWdodDoyNzZweDsgd2lkdGg6NDQxcHhcIiBcLz5GaWd1cmUgMSBpcyBhbiBleGFtcGxlIHdoZXJlIHRoZSB0b3RhbCBtYXR0cmVzcyBpcyBhIDYgJnRpbWVzOyAxMSBncmlkIGFuZCB0aGVyZSBhcmUgZm91ciBzdGFpbnMgbG9jYXRlZCBhdCB1bml0IHNxdWFyZXMgd2hvc2UgY29vcmRpbmF0ZXMgYXJlICg0LCAzKSwgKDYsIDUpLCAoMywgNiksIGFuZCAoNCwgNyksIHJlc3BlY3RpdmVseS4gSW4gdGhpcyBjYXNlLCB0d28gY2xlYW4tbWF0dHJlc3Mtc3F1YXJlcyB3aWxsIHN1ZmZpY2UuPFwvcD5cclxuXHJcbjxwPkdpdmVuIHRoZSBzaXplIG9mIHRoZSBtYXR0cmVzcyBhbmQgdGhlIGNvb3JkaW5hdGVzIG9mIHRoZSB1bml0IHNxdWFyZXMgd2hlcmUgc3RhaW5zIGFyZSBsb2NhdGVkLCB5b3UgYXJlIHRvIHdyaXRlIGEgcHJvZ3JhbSB0aGF0IGNvbXB1dGVzIHRoZSBtaW5pbXVtIG51bWJlciBvZiBjbGVhbi1tYXR0cmVzcy1zcXVhcmVzIHRvIGJlIHVzZWQuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gcmVhZCBmcm9tIHN0YW5kYXJkIGlucHV0LiBUaGUgaW5wdXQgY29uc2lzdHMgb2YgVCB0ZXN0IGNhc2VzLiBUaGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgVCBpcyBnaXZlbiBpbiB0aGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQuIEVhY2ggdGVzdCBjYXNlIHN0YXJ0cyB3aXRoIGludGVnZXJzIG0gYW5kIG4sIGdpdmluZyB0aGUgdmVydGljYWwgYW5kIGhvcml6b250YWwgc2l6ZSBvZiB0aGUgbWF0dHJlc3MsIHJlc3BlY3RpdmVseSwgd2hlcmUgMyAmbGU7IG0gJmxlOyAxMCBhbmQgMyAmbGU7IG4gJmxlOyAxLDAwMC4gSW4gdGhlIG5leHQgbGluZSwgYSBub25uZWdhdGl2ZSBpbnRlZ2VyIGMgaXMgZ2l2ZW4sIGluZGljYXRpbmcgdGhlIG51bWJlciBvZiB1bml0IHNxdWFyZXMgd2hlcmUgc3RhaW5zIGFyZSBsb2NhdGVkLiBJbiB0aGUgbmV4dCBjIGxpbmVzLCB0aGUgY29vcmRpbmF0ZXMgb2YgdGhlIHN0YWlucyBhcmUgZ2l2ZW4gb25lIHBlciBsaW5lLiBJdCBhbHdheXMgaG9sZHMgdGhhdCAwICZsZTsgYyAmbGU7IG1uLiBBbHNvLCB0aGUgY29vcmRpbmF0ZXMgZ2l2ZW4gYXJlIGFsbCBkaWZmZXJlbnQgYW5kIGFyZSBhbGwgb24gdGhlIG1hdHRyZXNzLiZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gd3JpdGUgdG8gc3RhbmRhcmQgb3V0cHV0LiBQcmludCBleGFjdGx5IG9uZSBsaW5lIGZvciBlYWNoIHRlc3QgY2FzZS4gVGhlIGxpbmUgc2hvdWxkIGNvbnRhaW4gYSBub25uZWdhdGl2ZSBpbnRlZ2VyLCB3aGljaCBpcyB0aGUgbWluaW11bSBudW1iZXIgb2YgY2xlYW4tbWF0dHJlc3Mtc3F1YXJlcyBuZWVkZWQgdG8gcmVtb3ZlIGFsbCBvZiB0aGUgc3RhaW5zLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==