시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 97 24 21 23.864%

문제

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

고대 문서 상자는 흥미로운 자물쇠가 달린 정교한 매커니즘으로 구성되어있다. 각각의 자물쇠는 너비 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+XHJcblxyXG48cD5cdWQ1NWNcdWM5MTFcdWQ2MDFcdWM3NDAgXHVkNTU4XHViMDk4XHVjNzU4IFx1YzVmNFx1YzFlMFx1YWMwMCBcdWI0NTAgXHVhYzFjIFx1Yzc3NFx1YzBjMVx1Yzc1OCBcdWM3OTBcdWJiM2NcdWMxZTBcdWI5N2MgXHVjNWY0IFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YmMxY1x1YWNhY1x1ZDU4OFx1YjJlNC4gXHVjNWY0XHVjMWUwXHViOTdjIFx1YjljY1x1YjRkY1x1YjI5NCBcdWM3OTFcdWM1YzVcdWM3NDAgXHViOWU0XHVjNmIwIFx1ZDc5OFx1YjRlNFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVjZDVjXHVjMThjXHVkNTVjXHVjNzU4IFx1YzVmNFx1YzFlMFx1Yjg1YyBcdWJhYThcdWI0ZTAgXHVjNzkwXHViYjNjXHVjMWUwXHViOTdjIFx1YzVmNFx1YWNlMFx1Yzc5MCBcdWQ1NWNcdWIyZTQuIFx1ZDU1Y1x1YzkxMVx1ZDYwMVx1Yzc1OCBcdWM3OTFcdWM1YzVcdWM3NDQgXHViMzVjXHVjNWI0XHVjOGZjXHVhZTMwIFx1YzcwNFx1ZDU3NCwgXHVjZDVjXHVjMThjIFx1YmE4NyBcdWFjMWNcdWM3NTggXHVjNWY0XHVjMWUwXHViOTdjIFx1YjljY1x1YjRlNFx1YzViNFx1YzU3YyBcdWQ1NThcdWIyOTRcdWM5YzAgXHVjNTRjXHViODI0XHVjOGZjXHVjNzkwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1Yzc5MFx1YmIzY1x1YzFlMFx1Yzc1OCBcdWIxMDhcdWJlNDQgVyAoMSAmbGU7IFcgJmxlOyAxMDxzdXA+ODxcL3N1cD4pLCBcdWM3OTBcdWJiM2NcdWMxZTBcdWM3NTggXHVhZTM4XHVjNzc0IEwgKDEgJmxlOyBMICZsZTsgMTAwMCksIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWM3OTBcdWJiM2NcdWMxZTBcdWM3NTggXHVhYzFjXHVjMjE4IE4gKDEgJmxlOyBOICZsZTsgMTAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyAyTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM3NDAgXHVjNzkwXHViYjNjXHVjMWUwXHVjNzU4IFx1YzgxNVx1YmNmNFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuIFx1YWMwMSBcdWM5MDRcdWM3NDAgV1x1YmNmNFx1YjJlNCBcdWM3OTFcdWM3NDAgTFx1YWMxY1x1Yzc1OCBcdWMyMThcdWI4NWMgXHVhZDZjXHVjMTMxXHViNDE4XHVjNWI0IFx1Yzc4OFx1YzczY1x1YmE3MCBcdWMwYzFcdWIyZThcdWJkODBcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzIxOFx1YzVmNFx1YWNmYyBcdWQ1NThcdWIyZThcdWJkODBcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzIxOFx1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWM3OTBcdWJiM2NcdWMxZTBcdWIyOTQgXHVjMGMxXHViMmU4XHViZDgwXHVjNjQwIFx1ZDU1OFx1YjJlOFx1YmQ4MCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHVjODAxXHVjNWI0XHViM2M0IDFjbVx1Yzc1OCBcdWJlNDggXHVhY2Y1XHVhYzA0XHVjNzc0IFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWQ1NWNcdWM5MTFcdWQ2MDFcdWM3NzQgXHViOWNjXHViNGU0XHVjNWI0XHVjNTdjIFx1ZDU2MCBcdWM1ZjRcdWMxZTBcdWM3NTggXHVjZDVjXHVjMThjIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjg5OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IktMRVRWQSIsImRlc2NyaXB0aW9uIjoiPHA+QXMgcHVuaXNobWVudCBmb3IgZGVzdHJveWluZyBoYWxmIG9mIGhpcyBjaXR5IHdpdGggaGlzIG1vbnN0ZXIgdHJ1Y2ssIE1pcmtvIG5vdyBoYXMgdG8gcGF5IG9mZiBoaXMgZGVwdCB0byBzb2NpZXR5LiBIZSB3b3JrcyBhcyBhbiBhc3Npc3RhbnQgZm9yIGEgZmFtb3VzIGFyY2hhZW9sb2dpc3QuIE9uZSBvZiBoaXMgZHV0aWVzIGluY2x1ZGUgY3JhZnRpbmcga2V5cyBmb3IgYW5jaWVudCBkb2N1bWVudCBib3hlcy48XC9wPlxyXG5cclxuPHA+SW4gYW5jaWVudCB0aW1lcyBkb2N1bWVudCBib3hlcyB3ZXJlIGxvY2tlZCB1c2luZyBlbGFib3JhdGUgbWVjaGFuaXNtcyB3aXRoIGludGVyZXN0aW5nIGxvY2tzLiBFYWNoIGxvY2sgaXMgTCBjZW50aW1ldGVycyBsb25nIGFuZCBXIGNlbnRpbWV0ZXJzIHdpZGUgYW5kIGNvbnNpc3RzIG9mIHRocmVlIHBhcnRzLCB0aGUgdXBwZXIgZWRnZSwgdGhlIGxvd2VyIGVkZ2UgYW5kIHRoZSBlbXB0eSBhcmVhIGJldHdlZW4gdGhlbS4gQm90aCBlZGdlcyBjYW4gYmUgcmVwcmVzZW50ZWQgYXMgYSBzZXF1ZW5jZSBvZiBMIG5vbm5lZ2F0aXZlIGludGVnZXJzOiByMSByMiByMyAuLi4gckwuIEVhY2ggbnVtYmVyIGluIHNlcXVlbmNlIHJlcHJlc2VudHMgdGhlIHdpZHRoIG9mIGVkZ2UgYXQgdGhhdCBwb2ludC48XC9wPlxyXG5cclxuPHA+VGhlIGtleSBmb3IgZWFjaCBsb2NrIGlzIGEgc21hbGwgY2xheSB0YWIsIGZpdHRpbmcgcGVyZmVjdGx5IGluIHRoZSBhcmVhIGJldHdlZW4gZWRnZXMuIFRoaXMgaW1hZ2Ugc2hvd3MgYSA3IGNtIGxvbmcsIDggY20gd2lkZSBsb2NrIGFsb25nIHdpdGggdGhlIGNvcnJlc3BvbmRpbmcga2V5LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2Jsb2Nrcy5wbmdcIiBzdHlsZT1cImhlaWdodDoyNTBweDsgd2lkdGg6Mjg4cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+VGhlIHNlcXVlbmNlIHJlcHJlc2VudGluZyB0aGUgdXBwZXIgZWRnZSBpcyBbMiwgMSwgMywgMiwgMywgMiwgM10sIGFuZCB0aGUgc2VxdWVuY2UgcmVwcmVzZW50aW5nIHRoZSBsb3dlciBlZGdlIGlzIFszLCA0LCAyLCAzLCAyLCAzLCA0XS4gTWlya28gbm90aWNlZCB0aGF0IHNvbWUga2V5cyBvcGVuIG1vcmUgdGhhbiBvbmUgbG9jay4gTWFraW5nIGtleXMgaXMgdGVkaW91cyB3b3JrIHNvIE1pcmtvIGFza2VkIHlvdSB0byBmaW5kIG91dCB3aGF0IGlzIHRoZSBtaW5pbWFsIG51bWJlciBvZiBkaWZmZXJlbnQga2V5cyBoZSBuZWVkcyB0byBtYWtlIGFuZCBzdGlsbCBiZSBhYmxlIHRvIG9wZW4gYWxsIG9mIHRoZSBsb2Nrcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhyZWUgaW50ZWdlcnMsIFcgKDEgJmxlOyBXICZsZTsgMTA8c3VwPjg8XC9zdXA+KSwgd2lkdGggb2YgYWxsIGxvY2tzLCBMICgxICZsZTsgTCAmbGU7IDEwMDApIGxlbmd0aCBvZiBhbGwgbG9ja3MsIGFuZCBOICgxICZsZTsgTiAmbGU7IDEwMCksIG51bWJlciBvZiBkaWZmZXJlbnQgbG9ja3MuPFwvcD5cclxuXHJcbjxwPk5leHQgMk4gbGluZXMgZGVzY3JpYmUgYWxsIGxvY2tzLiBFYWNoIGxpbmUgY29udGFpbnMgZXhhY3RseSBMIG51bWJlcnMgc21hbGxlciB0aGFuIFcuIEVhY2ggcGFpciBvZiBsaW5lcyBkZXNjcmliZXMgb25lIGxvY2suIFRoZSBmaXJzdCBsaW5lIGluIG9uZSBwYWlyIGRlc2NyaWJlcyB0aGUgdXBwZXIgZWRnZSwgYW5kIHRoZSBzZWNvbmQgbGluZSB0aGUgbG93ZXIgZWRnZS4gVGhlcmUgc2hhbGwgYWx3YXlzIGJlIGF0IGxlYXN0IDEgY20gb2YgZW1wdHkgc3BhY2UgYmV0d2VlbiBib3RoIGVkZ2VzIG9uIGFsbCBsb2Nrcy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBpbnB1dCBzaG91bGQgY29udGFpbiBhIHNpbmdsZSBpbnRlZ2VyLCB0aGUgbWluaW1hbCBudW1iZXIgb2YgZGlmZmVyZW50IGtleXMgTWlya28gbmVlZHMgdG8gY3JhZnQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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