Ancient Lock

An old document chest is fitted with intricate locks. Each lock is a rectangle $W$ cm wide and $L$ cm tall, and consists of an upper part, a lower part, and the empty space between them.

Each lock is described by two sequences of $L$ non-negative integers. In row $i$, the upper part extends $a_i$ cm inward from the left edge and the lower part extends $b_i$ cm inward from the right edge, leaving $W - a_i - b_i$ cm of empty space between them.

A key that fits a lock is a clay tab that fills this empty space exactly. Because a key is a single rigid piece, it can only be slid in with a horizontal shift. Hence two locks are opened by the same key if and only if one is a horizontal translation of the other: there exists an integer $d$ such that $a'_i = a_i + d$ and $b'_i = b_i - d$ for every $i$.

The figure below shows an example lock of width 8 cm and height 7 cm together with a matching key. Its upper sequence is $\{2, 1, 3, 2, 3, 2, 3\}$ and its lower sequence is $\{3, 4, 2, 3, 2, 3, 4\}$.

A single key may open two or more locks. To minimize the number of keys you must craft, determine the minimum number of keys needed to open all of the given locks.

The first line contains the lock width $W$ ($1 \le W \le 10^8$), the height $L$ ($1 \le L \le 1000$), and the number of locks $N$ ($1 \le N \le 100$), separated by spaces.

The next $2N$ lines describe the locks. Each lock is given on two lines: the first line is the upper sequence $a_1, a_2, \dots, a_L$ and the second line is the lower sequence $b_1, b_2, \dots, b_L$. Every value is at least $0$ and less than $W$, and in every row there is at least 1 cm of empty space between the upper and lower parts (that is, $a_i + b_i < W$ for all $i$).

Print, on a single line, the minimum number of keys needed to open all of the locks.