고대 자물쇠

오래된 문서 상자에는 정교한 자물쇠가 달려 있다. 각 자물쇠는 너비 $W$ cm, 높이 $L$ cm의 직사각형이며, 상단부, 하단부, 그리고 그 둘 사이의 빈 공간으로 이루어진다.

각 자물쇠는 길이 $L$인 두 개의 음이 아닌 정수 수열로 표현된다. $i$번째 줄에서 상단부는 왼쪽 가장자리에서 $a_i$ cm만큼, 하단부는 오른쪽 가장자리에서 $b_i$ cm만큼 안쪽으로 뻗어 있고, 그 사이에는 $W - a_i - b_i$ cm의 빈 공간이 남는다.

자물쇠에 맞는 열쇠는 이 빈 공간에 정확히 들어맞는 점토 탭이다. 열쇠는 하나의 단단한 조각이라 좌우로 평행하게만 밀어 넣을 수 있다. 따라서 두 자물쇠는 한쪽이 다른 쪽의 수평 평행이동일 때, 그리고 그때에만 같은 열쇠로 열린다. 즉 어떤 정수 $d$가 존재하여 모든 $i$에 대해 $a'_i = a_i + d$이고 $b'_i = b_i - d$이면, 두 자물쇠는 같은 열쇠로 열린다.

아래 그림은 너비 8 cm, 높이 7 cm인 자물쇠와 그에 맞는 열쇠의 예시이다. 상단부 수열은 $\{2, 1, 3, 2, 3, 2, 3\}$, 하단부 수열은 $\{3, 4, 2, 3, 2, 3, 4\}$이다.

하나의 열쇠로 두 개 이상의 자물쇠를 열 수도 있다. 만들어야 하는 열쇠의 수를 최소로 할 때, 주어진 모든 자물쇠를 열기 위해 만들어야 하는 열쇠의 최소 개수를 구하라.

첫째 줄에 자물쇠의 너비 $W$ ($1 \le W \le 10^8$), 높이 $L$ ($1 \le L \le 1000$), 자물쇠의 개수 $N$ ($1 \le N \le 100$)이 공백으로 구분되어 주어진다.

이어지는 $2N$개의 줄은 자물쇠들의 정보이다. 각 자물쇠마다 두 줄이 주어지며, 첫째 줄은 상단부 수열 $a_1, a_2, \dots, a_L$, 둘째 줄은 하단부 수열 $b_1, b_2, \dots, b_L$이다. 각 수는 $0$ 이상 $W$ 미만이고, 모든 줄에서 상단부와 하단부 사이에는 적어도 1 cm의 빈 공간이 있다 (즉 모든 $i$에 대해 $a_i + b_i < W$).

모든 자물쇠를 열기 위해 만들어야 하는 열쇠의 최소 개수를 한 줄에 출력한다.