시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 125 28 24 21.818%

문제

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

고대 문서 상자는 흥미로운 자물쇠가 달린 정교한 매커니즘으로 구성되어있다. 각각의 자물쇠는 너비 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
W3sicHJvYmxlbV9pZCI6IjI4OTgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjZTBcdWIzMDAgXHVjNzkwXHViYjNjXHVjMWUwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ1NWNcdWM5MTFcdWQ2MDFcdWM3NDAgXHVjNzkwXHVjMmUwXHVjNzU4IFx1YmFhY1x1YzJhNFx1ZDEzMCBcdWQyYjhcdWI3ZWRcdWM3M2NcdWI4NWMgXHViM2M0XHVjMmRjXHVjNzU4IFx1YzgwOFx1YmMxOFx1Yzc0NCBcdWIwYTBcdWI4MjRcdWJjODRcdWI5YjAgXHViMzAwXHVhYzAwXHViODVjIFx1YzcyMFx1YmE4NVx1ZDU1YyBcdWFjZTBcdWFjZTBcdWQ1NTlcdWM3OTBcdWM3NTggXHVjODcwXHVjMjE4XHViODVjIFx1Yzc3Y1x1ZDU1OFx1YWM4YyBcdWI0MThcdWM1YzhcdWIyZTQuIFx1YWRmOFx1Yzc1OCBcdWM3ODRcdWJiMzQgXHVjOTExIFx1ZDU1OFx1YjA5OFx1YjI5NCBcdWFjZTBcdWIzMDAgXHViYjM4XHVjMTFjIFx1YzBjMVx1Yzc5MFx1Yzc1OCBcdWM1ZjRcdWMxZTBcdWI5N2MgXHViOWNjXHViNGRjXHViMjk0IFx1Yzc3Y1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhY2UwXHViMzAwIFx1YmIzOFx1YzExYyBcdWMwYzFcdWM3OTBcdWIyOTQgXHVkNzY1XHViYmY4XHViODVjXHVjNmI0IFx1Yzc5MFx1YmIzY1x1YzFlMFx1YWMwMCBcdWIyZWNcdWI5YjAgXHVjODE1XHVhZDUwXHVkNTVjIFx1YjllNFx1Y2VlNFx1YjJjOFx1Yzk5OFx1YzczY1x1Yjg1YyBcdWFkNmNcdWMxMzFcdWI0MThcdWM1YjRcdWM3ODhcdWIyZTQuIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWM3OTBcdWJiM2NcdWMxZTBcdWIyOTQgXHViMTA4XHViZTQ0IFcgY20sIFx1YjE5Mlx1Yzc3NCBMIGNtIFx1Yzc3NFx1YmE3MCBcdWMwYzFcdWIyZThcdWJkODAsIFx1ZDU1OFx1YjJlOFx1YmQ4MCwgXHVhZGY4XHViOWFjXHVhY2UwIFx1Yzc3NCBcdWI0NTggXHVjMGFjXHVjNzc0XHVjNzU4IFx1YmU0OCBcdWFjZjVcdWFjMDRcdWM3M2NcdWI4NWMgXHVhZDZjXHVjMTMxXHViNDE4XHVjNWI0XHVjNzg4XHViMmU0LiBcdWMwYzFcdWIyZThcdWJkODBcdWM2NDAgXHVkNTU4XHViMmU4XHViZDgwXHViMjk0IFx1Yzc0Y1x1Yzc3NFx1YzU0NFx1YjJjYyBcdWM4MTVcdWMyMThcdWM3NTggXHVjMjE4XHVjNWY0IHIxLCByMiwgcjMsIC4uLiwgckxcdWI4NWMgXHViMDk4XHVkMGMwXHViMGI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVjNzkwXHViYjNjXHVjMWUwXHVjNWQwIFx1YjlkZVx1YjI5NCBcdWM1ZjRcdWMxZTBcdWIyOTQgXHVhYzAwXHVjN2E1XHVjNzkwXHViOWFjIFx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWFjZjVcdWFjMDRcdWM1ZDAgXHVjNjQ0XHViY2JkXHVkNTU4XHVhYzhjIFx1YjlkZVx1YjI5NCBcdWM3OTFcdWM3NDAgXHVjODEwXHVkMWEwIFx1ZDBlZFx1YzczY1x1Yjg1YyBcdWI0MThcdWM1YjRcdWM3ODhcdWIyZTQuIFx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWM3NDAgN2NtIFggOGNtIFx1ZDYxNVx1ZDBkY1x1Yzc1OCBcdWM3OTBcdWJiM2NcdWMxZTBcdWM2NDAgXHVjNzc0XHVjNWQwIFx1YjlkZVx1YjI5NCBcdWM1ZjRcdWMxZTBcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiBcdWMwYzFcdWIyZThcdWJkODBcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzIxOFx1YzVmNFx1Yzc0MCB7MiwgMSwgMywgMiwgMywgMiwgM31cdWM3NzRcdWJhNzAgXHVkNTU4XHViMmU4XHViZDgwXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWMyMThcdWM1ZjRcdWM3NDAgezMsIDQsIDIsIDMsIDIsIDMsIDR9XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2Jsb2Nrcy5wbmdcIiBzdHlsZT1cImhlaWdodDoyNTBweDsgd2lkdGg6Mjg4cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVkNTVjXHVjOTExXHVkNjAxXHVjNzQwIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWM1ZjRcdWMxZTBcdWFjMDAgXHViNDUwIFx1YWMxYyBcdWM3NzRcdWMwYzFcdWM3NTggXHVjNzkwXHViYjNjXHVjMWUwXHViOTdjIFx1YzVmNCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0XHViMjk0IFx1YWM4M1x1Yzc0NCBcdWJjMWNcdWFjYWNcdWQ1ODhcdWIyZTQuIFx1YzVmNFx1YzFlMFx1Yjk3YyBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHVjNzkxXHVjNWM1XHVjNzQwIFx1YjllNFx1YzZiMCBcdWQ3OThcdWI0ZTRcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1Y2Q1Y1x1YzE4Y1x1ZDU1Y1x1Yzc1OCBcdWM1ZjRcdWMxZTBcdWI4NWMgXHViYWE4XHViNGUwIFx1Yzc5MFx1YmIzY1x1YzFlMFx1Yjk3YyBcdWM1ZjRcdWFjZTBcdWM3OTAgXHVkNTVjXHViMmU0LiBcdWQ1NWNcdWM5MTFcdWQ2MDFcdWM3NTggXHVjNzkxXHVjNWM1XHVjNzQ0IFx1YjM1Y1x1YzViNFx1YzhmY1x1YWUzMCBcdWM3MDRcdWQ1NzQsIFx1Y2Q1Y1x1YzE4YyBcdWJhODcgXHVhYzFjXHVjNzU4IFx1YzVmNFx1YzFlMFx1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWM1N2MgXHVkNTU4XHViMjk0XHVjOWMwIFx1YzU0Y1x1YjgyNFx1YzhmY1x1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM3OTBcdWJiM2NcdWMxZTBcdWM3NTggXHViMTA4XHViZTQ0IFcgKDEgJmxlOyBXICZsZTsgMTA8c3VwPjg8XC9zdXA+KSwgXHVjNzkwXHViYjNjXHVjMWUwXHVjNzU4IFx1YWUzOFx1Yzc3NCBMICgxICZsZTsgTCAmbGU7IDEwMDApLCBcdWFkZjhcdWI5YWNcdWFjZTAgXHVjNzkwXHViYjNjXHVjMWUwXHVjNzU4IFx1YWMxY1x1YzIxOCBOICgxICZsZTsgTiAmbGU7IDEwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgMk5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNzQwIFx1Yzc5MFx1YmIzY1x1YzFlMFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiBcdWFjMDEgXHVjOTA0XHVjNzQwIFdcdWJjZjRcdWIyZTQgXHVjNzkxXHVjNzQwIExcdWFjMWNcdWM3NTggXHVjMjE4XHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxOFx1YzViNCBcdWM3ODhcdWM3M2NcdWJhNzAgXHVjMGMxXHViMmU4XHViZDgwXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWMyMThcdWM1ZjRcdWFjZmMgXHVkNTU4XHViMmU4XHViZDgwXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWMyMThcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWJhYThcdWI0ZTAgXHVjNzkwXHViYjNjXHVjMWUwXHViMjk0IFx1YzBjMVx1YjJlOFx1YmQ4MFx1YzY0MCBcdWQ1NThcdWIyZThcdWJkODAgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YzgwMVx1YzViNFx1YjNjNCAxY21cdWM3NTggXHViZTQ4IFx1YWNmNVx1YWMwNFx1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVkNTVjXHVjOTExXHVkNjAxXHVjNzc0IFx1YjljY1x1YjRlNFx1YzViNFx1YzU3YyBcdWQ1NjAgXHVjNWY0XHVjMWUwXHVjNzU4IFx1Y2Q1Y1x1YzE4YyBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI4OTgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJLTEVUVkEiLCJkZXNjcmlwdGlvbiI6IjxwPkFzIHB1bmlzaG1lbnQgZm9yIGRlc3Ryb3lpbmcgaGFsZiBvZiBoaXMgY2l0eSB3aXRoIGhpcyBtb25zdGVyIHRydWNrLCBNaXJrbyBub3cgaGFzIHRvIHBheSBvZmYgaGlzIGRlcHQgdG8gc29jaWV0eS4gSGUgd29ya3MgYXMgYW4gYXNzaXN0YW50IGZvciBhIGZhbW91cyBhcmNoYWVvbG9naXN0LiBPbmUgb2YgaGlzIGR1dGllcyBpbmNsdWRlIGNyYWZ0aW5nIGtleXMgZm9yIGFuY2llbnQgZG9jdW1lbnQgYm94ZXMuPFwvcD5cclxuXHJcbjxwPkluIGFuY2llbnQgdGltZXMgZG9jdW1lbnQgYm94ZXMgd2VyZSBsb2NrZWQgdXNpbmcgZWxhYm9yYXRlIG1lY2hhbmlzbXMgd2l0aCBpbnRlcmVzdGluZyBsb2Nrcy4gRWFjaCBsb2NrIGlzIEwgY2VudGltZXRlcnMgbG9uZyBhbmQgVyBjZW50aW1ldGVycyB3aWRlIGFuZCBjb25zaXN0cyBvZiB0aHJlZSBwYXJ0cywgdGhlIHVwcGVyIGVkZ2UsIHRoZSBsb3dlciBlZGdlIGFuZCB0aGUgZW1wdHkgYXJlYSBiZXR3ZWVuIHRoZW0uIEJvdGggZWRnZXMgY2FuIGJlIHJlcHJlc2VudGVkIGFzIGEgc2VxdWVuY2Ugb2YgTCBub25uZWdhdGl2ZSBpbnRlZ2VyczogcjEgcjIgcjMgLi4uIHJMLiBFYWNoIG51bWJlciBpbiBzZXF1ZW5jZSByZXByZXNlbnRzIHRoZSB3aWR0aCBvZiBlZGdlIGF0IHRoYXQgcG9pbnQuPFwvcD5cclxuXHJcbjxwPlRoZSBrZXkgZm9yIGVhY2ggbG9jayBpcyBhIHNtYWxsIGNsYXkgdGFiLCBmaXR0aW5nIHBlcmZlY3RseSBpbiB0aGUgYXJlYSBiZXR3ZWVuIGVkZ2VzLiBUaGlzIGltYWdlIHNob3dzIGEgNyBjbSBsb25nLCA4IGNtIHdpZGUgbG9jayBhbG9uZyB3aXRoIHRoZSBjb3JyZXNwb25kaW5nIGtleS48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9ibG9ja3MucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjUwcHg7IHdpZHRoOjI4OHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlRoZSBzZXF1ZW5jZSByZXByZXNlbnRpbmcgdGhlIHVwcGVyIGVkZ2UgaXMgWzIsIDEsIDMsIDIsIDMsIDIsIDNdLCBhbmQgdGhlIHNlcXVlbmNlIHJlcHJlc2VudGluZyB0aGUgbG93ZXIgZWRnZSBpcyBbMywgNCwgMiwgMywgMiwgMywgNF0uIE1pcmtvIG5vdGljZWQgdGhhdCBzb21lIGtleXMgb3BlbiBtb3JlIHRoYW4gb25lIGxvY2suIE1ha2luZyBrZXlzIGlzIHRlZGlvdXMgd29yayBzbyBNaXJrbyBhc2tlZCB5b3UgdG8gZmluZCBvdXQgd2hhdCBpcyB0aGUgbWluaW1hbCBudW1iZXIgb2YgZGlmZmVyZW50IGtleXMgaGUgbmVlZHMgdG8gbWFrZSBhbmQgc3RpbGwgYmUgYWJsZSB0byBvcGVuIGFsbCBvZiB0aGUgbG9ja3MuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5GaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRocmVlIGludGVnZXJzLCBXICgxICZsZTsgVyAmbGU7IDEwPHN1cD44PFwvc3VwPiksIHdpZHRoIG9mIGFsbCBsb2NrcywgTCAoMSAmbGU7IEwgJmxlOyAxMDAwKSBsZW5ndGggb2YgYWxsIGxvY2tzLCBhbmQgTiAoMSAmbGU7IE4gJmxlOyAxMDApLCBudW1iZXIgb2YgZGlmZmVyZW50IGxvY2tzLjxcL3A+XHJcblxyXG48cD5OZXh0IDJOIGxpbmVzIGRlc2NyaWJlIGFsbCBsb2Nrcy4gRWFjaCBsaW5lIGNvbnRhaW5zIGV4YWN0bHkgTCBudW1iZXJzIHNtYWxsZXIgdGhhbiBXLiBFYWNoIHBhaXIgb2YgbGluZXMgZGVzY3JpYmVzIG9uZSBsb2NrLiBUaGUgZmlyc3QgbGluZSBpbiBvbmUgcGFpciBkZXNjcmliZXMgdGhlIHVwcGVyIGVkZ2UsIGFuZCB0aGUgc2Vjb25kIGxpbmUgdGhlIGxvd2VyIGVkZ2UuIFRoZXJlIHNoYWxsIGFsd2F5cyBiZSBhdCBsZWFzdCAxIGNtIG9mIGVtcHR5IHNwYWNlIGJldHdlZW4gYm90aCBlZGdlcyBvbiBhbGwgbG9ja3MuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2YgaW5wdXQgc2hvdWxkIGNvbnRhaW4gYSBzaW5nbGUgaW50ZWdlciwgdGhlIG1pbmltYWwgbnVtYmVyIG9mIGRpZmZlcmVudCBrZXlzIE1pcmtvIG5lZWRzIHRvIGNyYWZ0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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