시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 57 12 12 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의 빈 공간이 존재한다.

출력

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

예제 입력

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

힌트

출처

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