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

문제

한중혁은 자신의 몬스터 트럭으로 도시의 절반을 날려버린 대가로 유명한 고고학자의 조수로 일하게 되었다. 그의 임무 중 하나는 고대 문서 상자의 열쇠를 만드는 일이다.

고대 문서 상자는 흥미로운 자물쇠가 달린 정교한 매커니즘으로 구성되어있다. 각각의 자물쇠는 너비 W cm, 높이 L cm 이며 상단부, 하단부, 그리고 이 둘 사이의 빈 공간으로 구성되어있다. 상단부와 하단부는 음이아닌 정수의 수열 r1, r2, r3, ..., rL로 나타내진다.

각 자물쇠에 맞는 열쇠는 가장자리 사이의 공간에 완벽하게 맞는 작은 점토 탭으로 되어있다. 아래 그림은 7cm X 8cm 형태의 자물쇠와 이에 맞는 열쇠를 나타낸다. 상단부를 나타내는 수열은 {2, 1, 3, 2, 3, 2, 3}이며 하단부를 나타내는 수열은 {3, 4, 2, 3, 2, 3, 4}이다.

한중혁은 하나의 열쇠가 두 개 이상의 자물쇠를 열 수도 있다는 것을 발견했다. 열쇠를 만드는 작업은 매우 힘들기 때문에 최소한의 열쇠로 모든 자물쇠를 열고자 한다. 한중혁의 작업을 덜어주기 위해, 최소 몇 개의 열쇠를 만들어야 하는지 알려주자.

입력

입력의 첫 번째 줄에는 자물쇠의 너비 W (1 ≤ W ≤ 108), 자물쇠의 길이 L (1 ≤ L ≤ 1000), 그리고 자물쇠의 개수 N (1 ≤ N ≤ 100)이 주어진다.

다음 2N개의 줄은 자물쇠의 정보를 나타낸다. 각 줄은 W보다 작은 L개의 수로 구성되어 있으며 상단부를 나타내는 수열과 하단부를 나타내는 수열이 주어진다. 모든 자물쇠는 상단부와 하단부 사이에 적어도 1cm의 빈 공간이 존재한다.

출력

한중혁이 만들어야 할 열쇠의 최소 개수를 출력한다.

예제 입력 1

8 7 2
2 1 3 2 3 2 3
3 4 2 3 2 3 4
3 2 4 3 4 3 4
2 3 1 2 1 2 3

예제 출력 1

1

예제 입력 2

8 4 4
3 3 3 3
3 3 3 3
2 2 2 2
4 4 4 4
1 2 3 4
4 3 2 1
1 1 1 1
5 5 5 5

예제 출력 2

2

예제 입력 3

100000000 2 2
88888888 88888888
4 4
4 4
88888888 88888888

예제 출력 3

1
W3sicHJvYmxlbV9pZCI6IjI4OTgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjZTBcdWIzMDAgXHVjNzkwXHViYjNjXHVjMWUwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ1NWNcdWM5MTFcdWQ2MDFcdWM3NDAgXHVjNzkwXHVjMmUwXHVjNzU4IFx1YmFhY1x1YzJhNFx1ZDEzMCBcdWQyYjhcdWI3ZWRcdWM3M2NcdWI4NWMgXHViM2M0XHVjMmRjXHVjNzU4IFx1YzgwOFx1YmMxOFx1Yzc0NCBcdWIwYTBcdWI4MjRcdWJjODRcdWI5YjAgXHViMzAwXHVhYzAwXHViODVjIFx1YzcyMFx1YmE4NVx1ZDU1YyBcdWFjZTBcdWFjZTBcdWQ1NTlcdWM3OTBcdWM3NTggXHVjODcwXHVjMjE4XHViODVjIFx1Yzc3Y1x1ZDU1OFx1YWM4YyBcdWI0MThcdWM1YzhcdWIyZTQuIFx1YWRmOFx1Yzc1OCBcdWM3ODRcdWJiMzQgXHVjOTExIFx1ZDU1OFx1YjA5OFx1YjI5NCBcdWFjZTBcdWIzMDAgXHViYjM4XHVjMTFjIFx1YzBjMVx1Yzc5MFx1Yzc1OCBcdWM1ZjRcdWMxZTBcdWI5N2MgXHViOWNjXHViNGRjXHViMjk0IFx1Yzc3Y1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhY2UwXHViMzAwIFx1YmIzOFx1YzExYyBcdWMwYzFcdWM3OTBcdWIyOTQgXHVkNzY1XHViYmY4XHViODVjXHVjNmI0IFx1Yzc5MFx1YmIzY1x1YzFlMFx1YWMwMCBcdWIyZWNcdWI5YjAgXHVjODE1XHVhZDUwXHVkNTVjIFx1YjllNFx1Y2VlNFx1YjJjOFx1Yzk5OFx1YzczY1x1Yjg1YyBcdWFkNmNcdWMxMzFcdWI0MThcdWM1YjRcdWM3ODhcdWIyZTQuIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWM3OTBcdWJiM2NcdWMxZTBcdWIyOTQgXHViMTA4XHViZTQ0IFcgY20sIFx1YjE5Mlx1Yzc3NCBMIGNtIFx1Yzc3NFx1YmE3MCBcdWMwYzFcdWIyZThcdWJkODAsIFx1ZDU1OFx1YjJlOFx1YmQ4MCwgXHVhZGY4XHViOWFjXHVhY2UwIFx1Yzc3NCBcdWI0NTggXHVjMGFjXHVjNzc0XHVjNzU4IFx1YmU0OCBcdWFjZjVcdWFjMDRcdWM3M2NcdWI4NWMgXHVhZDZjXHVjMTMxXHViNDE4XHVjNWI0XHVjNzg4XHViMmU0LiBcdWMwYzFcdWIyZThcdWJkODBcdWM2NDAgXHVkNTU4XHViMmU4XHViZDgwXHViMjk0IFx1Yzc0Y1x1Yzc3NFx1YzU0NFx1YjJjYyBcdWM4MTVcdWMyMThcdWM3NTggXHVjMjE4XHVjNWY0IHIxLCByMiwgcjMsIC4uLiwgckxcdWI4NWMgXHViMDk4XHVkMGMwXHViMGI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVjNzkwXHViYjNjXHVjMWUwXHVjNWQwIFx1YjlkZVx1YjI5NCBcdWM1ZjRcdWMxZTBcdWIyOTQgXHVhYzAwXHVjN2E1XHVjNzkwXHViOWFjIFx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWFjZjVcdWFjMDRcdWM1ZDAgXHVjNjQ0XHViY2JkXHVkNTU4XHVhYzhjIFx1YjlkZVx1YjI5NCBcdWM3OTFcdWM3NDAgXHVjODEwXHVkMWEwIFx1ZDBlZFx1YzczY1x1Yjg1YyBcdWI0MThcdWM1YjRcdWM3ODhcdWIyZTQuIFx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWM3NDAgN2NtIFggOGNtIFx1ZDYxNVx1ZDBkY1x1Yzc1OCBcdWM3OTBcdWJiM2NcdWMxZTBcdWM2NDAgXHVjNzc0XHVjNWQwIFx1YjlkZVx1YjI5NCBcdWM1ZjRcdWMxZTBcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiBcdWMwYzFcdWIyZThcdWJkODBcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzIxOFx1YzVmNFx1Yzc0MCB7MiwgMSwgMywgMiwgMywgMiwgM31cdWM3NzRcdWJhNzAgXHVkNTU4XHViMmU4XHViZDgwXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWMyMThcdWM1ZjRcdWM3NDAgezMsIDQsIDIsIDMsIDIsIDMsIDR9XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcLzgzNzdjNDk1LTBjMTItNGE2Yi1iMTA0LTRhOTYzNzY4MzcxM1wvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogMjUzcHg7IGhlaWdodDogMjIzcHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1ZDU1Y1x1YzkxMVx1ZDYwMVx1Yzc0MCBcdWQ1NThcdWIwOThcdWM3NTggXHVjNWY0XHVjMWUwXHVhYzAwIFx1YjQ1MCBcdWFjMWMgXHVjNzc0XHVjMGMxXHVjNzU4IFx1Yzc5MFx1YmIzY1x1YzFlMFx1Yjk3YyBcdWM1ZjQgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNFx1YjI5NCBcdWFjODNcdWM3NDQgXHViYzFjXHVhY2FjXHVkNTg4XHViMmU0LiBcdWM1ZjRcdWMxZTBcdWI5N2MgXHViOWNjXHViNGRjXHViMjk0IFx1Yzc5MVx1YzVjNVx1Yzc0MCBcdWI5ZTRcdWM2YjAgXHVkNzk4XHViNGU0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWNkNWNcdWMxOGNcdWQ1NWNcdWM3NTggXHVjNWY0XHVjMWUwXHViODVjIFx1YmFhOFx1YjRlMCBcdWM3OTBcdWJiM2NcdWMxZTBcdWI5N2MgXHVjNWY0XHVhY2UwXHVjNzkwIFx1ZDU1Y1x1YjJlNC4gXHVkNTVjXHVjOTExXHVkNjAxXHVjNzU4IFx1Yzc5MVx1YzVjNVx1Yzc0NCBcdWIzNWNcdWM1YjRcdWM4ZmNcdWFlMzAgXHVjNzA0XHVkNTc0LCBcdWNkNWNcdWMxOGMgXHViYTg3IFx1YWMxY1x1Yzc1OCBcdWM1ZjRcdWMxZTBcdWI5N2MgXHViOWNjXHViNGU0XHVjNWI0XHVjNTdjIFx1ZDU1OFx1YjI5NFx1YzljMCBcdWM1NGNcdWI4MjRcdWM4ZmNcdWM3OTAuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NTggXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNzkwXHViYjNjXHVjMWUwXHVjNzU4IFx1YjEwOFx1YmU0NCBXICgxICZsZTsgVyAmbGU7IDEwPHN1cD44PFwvc3VwPiksIFx1Yzc5MFx1YmIzY1x1YzFlMFx1Yzc1OCBcdWFlMzhcdWM3NzQgTCAoMSAmbGU7IEwgJmxlOyAxMDAwKSwgXHVhZGY4XHViOWFjXHVhY2UwIFx1Yzc5MFx1YmIzY1x1YzFlMFx1Yzc1OCBcdWFjMWNcdWMyMTggTiAoMSAmbGU7IE4gJmxlOyAxMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIDJOXHVhYzFjXHVjNzU4IFx1YzkwNFx1Yzc0MCBcdWM3OTBcdWJiM2NcdWMxZTBcdWM3NTggXHVjODE1XHViY2Y0XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC4gXHVhYzAxIFx1YzkwNFx1Yzc0MCBXXHViY2Y0XHViMmU0IFx1Yzc5MVx1Yzc0MCBMXHVhYzFjXHVjNzU4IFx1YzIxOFx1Yjg1YyBcdWFkNmNcdWMxMzFcdWI0MThcdWM1YjQgXHVjNzg4XHVjNzNjXHViYTcwIFx1YzBjMVx1YjJlOFx1YmQ4MFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjMjE4XHVjNWY0XHVhY2ZjIFx1ZDU1OFx1YjJlOFx1YmQ4MFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjMjE4XHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViYWE4XHViNGUwIFx1Yzc5MFx1YmIzY1x1YzFlMFx1YjI5NCBcdWMwYzFcdWIyZThcdWJkODBcdWM2NDAgXHVkNTU4XHViMmU4XHViZDgwIFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWM4MDFcdWM1YjRcdWIzYzQgMWNtXHVjNzU4IFx1YmU0OCBcdWFjZjVcdWFjMDRcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1ZDU1Y1x1YzkxMVx1ZDYwMVx1Yzc3NCBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWM1N2MgXHVkNTYwIFx1YzVmNFx1YzFlMFx1Yzc1OCBcdWNkNWNcdWMxOGMgXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyODk4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiS0xFVFZBIiwiZGVzY3JpcHRpb24iOiI8cD5BcyBwdW5pc2htZW50IGZvciBkZXN0cm95aW5nIGhhbGYgb2YgaGlzIGNpdHkgd2l0aCBoaXMgbW9uc3RlciB0cnVjaywgTWlya28gbm93IGhhcyB0byBwYXkgb2ZmIGhpcyBkZXB0IHRvIHNvY2lldHkuIEhlIHdvcmtzIGFzIGFuIGFzc2lzdGFudCBmb3IgYSBmYW1vdXMgYXJjaGFlb2xvZ2lzdC4gT25lIG9mIGhpcyBkdXRpZXMgaW5jbHVkZSBjcmFmdGluZyBrZXlzIGZvciBhbmNpZW50IGRvY3VtZW50IGJveGVzLjxcL3A+XHJcblxyXG48cD5JbiBhbmNpZW50IHRpbWVzIGRvY3VtZW50IGJveGVzIHdlcmUgbG9ja2VkIHVzaW5nIGVsYWJvcmF0ZSBtZWNoYW5pc21zIHdpdGggaW50ZXJlc3RpbmcgbG9ja3MuIEVhY2ggbG9jayBpcyBMIGNlbnRpbWV0ZXJzIGxvbmcgYW5kIFcgY2VudGltZXRlcnMgd2lkZSBhbmQgY29uc2lzdHMgb2YgdGhyZWUgcGFydHMsIHRoZSB1cHBlciBlZGdlLCB0aGUgbG93ZXIgZWRnZSBhbmQgdGhlIGVtcHR5IGFyZWEgYmV0d2VlbiB0aGVtLiBCb3RoIGVkZ2VzIGNhbiBiZSByZXByZXNlbnRlZCBhcyBhIHNlcXVlbmNlIG9mIEwgbm9ubmVnYXRpdmUgaW50ZWdlcnM6IHIxIHIyIHIzIC4uLiByTC4gRWFjaCBudW1iZXIgaW4gc2VxdWVuY2UgcmVwcmVzZW50cyB0aGUgd2lkdGggb2YgZWRnZSBhdCB0aGF0IHBvaW50LjxcL3A+XHJcblxyXG48cD5UaGUga2V5IGZvciBlYWNoIGxvY2sgaXMgYSBzbWFsbCBjbGF5IHRhYiwgZml0dGluZyBwZXJmZWN0bHkgaW4gdGhlIGFyZWEgYmV0d2VlbiBlZGdlcy4gVGhpcyBpbWFnZSBzaG93cyBhIDcgY20gbG9uZywgOCBjbSB3aWRlIGxvY2sgYWxvbmcgd2l0aCB0aGUgY29ycmVzcG9uZGluZyBrZXkuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvODM3N2M0OTUtMGMxMi00YTZiLWIxMDQtNGE5NjM3NjgzNzEzXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiAyNTNweDsgaGVpZ2h0OiAyMjNweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+VGhlIHNlcXVlbmNlIHJlcHJlc2VudGluZyB0aGUgdXBwZXIgZWRnZSBpcyBbMiwgMSwgMywgMiwgMywgMiwgM10sIGFuZCB0aGUgc2VxdWVuY2UgcmVwcmVzZW50aW5nIHRoZSBsb3dlciBlZGdlIGlzIFszLCA0LCAyLCAzLCAyLCAzLCA0XS4gTWlya28gbm90aWNlZCB0aGF0IHNvbWUga2V5cyBvcGVuIG1vcmUgdGhhbiBvbmUgbG9jay4gTWFraW5nIGtleXMgaXMgdGVkaW91cyB3b3JrIHNvIE1pcmtvIGFza2VkIHlvdSB0byBmaW5kIG91dCB3aGF0IGlzIHRoZSBtaW5pbWFsIG51bWJlciBvZiBkaWZmZXJlbnQga2V5cyBoZSBuZWVkcyB0byBtYWtlIGFuZCBzdGlsbCBiZSBhYmxlIHRvIG9wZW4gYWxsIG9mIHRoZSBsb2Nrcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhyZWUgaW50ZWdlcnMsIFcgKDEgJmxlOyBXICZsZTsgMTA8c3VwPjg8XC9zdXA+KSwgd2lkdGggb2YgYWxsIGxvY2tzLCBMICgxICZsZTsgTCAmbGU7IDEwMDApIGxlbmd0aCBvZiBhbGwgbG9ja3MsIGFuZCBOICgxICZsZTsgTiAmbGU7IDEwMCksIG51bWJlciBvZiBkaWZmZXJlbnQgbG9ja3MuPFwvcD5cclxuXHJcbjxwPk5leHQgMk4gbGluZXMgZGVzY3JpYmUgYWxsIGxvY2tzLiBFYWNoIGxpbmUgY29udGFpbnMgZXhhY3RseSBMIG51bWJlcnMgc21hbGxlciB0aGFuIFcuIEVhY2ggcGFpciBvZiBsaW5lcyBkZXNjcmliZXMgb25lIGxvY2suIFRoZSBmaXJzdCBsaW5lIGluIG9uZSBwYWlyIGRlc2NyaWJlcyB0aGUgdXBwZXIgZWRnZSwgYW5kIHRoZSBzZWNvbmQgbGluZSB0aGUgbG93ZXIgZWRnZS4gVGhlcmUgc2hhbGwgYWx3YXlzIGJlIGF0IGxlYXN0IDEgY20gb2YgZW1wdHkgc3BhY2UgYmV0d2VlbiBib3RoIGVkZ2VzIG9uIGFsbCBsb2Nrcy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBpbnB1dCBzaG91bGQgY29udGFpbiBhIHNpbmdsZSBpbnRlZ2VyLCB0aGUgbWluaW1hbCBudW1iZXIgb2YgZGlmZmVyZW50IGtleXMgTWlya28gbmVlZHMgdG8gY3JhZnQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Contest > Croatian Open Competition in Informatics > COCI 2009/2010 > Contest #5 3번