作为对他用怪兽卡车摧毁了半个城市的惩罚，Mirko 现在必须偿还他对社会的债务。他现在担任一位著名考古学家的助手。他的职责之一是为古老的文献箱制作钥匙。

在古代，文献箱是用带有有趣锁的复杂机构锁上的。每个锁长 $L$ 厘米，宽 $W$ 厘米，由三部分组成：上边缘、下边缘以及它们之间的空白区域。两个边缘都可以表示为含有 $L$ 个非负整数的序列：$r_1\ r_2\ r_3\ \dots\ r_L$。序列中的每个数字代表该点处边缘的宽度。

每个锁的钥匙是一个小泥片，完美地贴合在边缘之间的区域。下图显示了一个长 $7\text{ cm}$、宽 $8\text{ cm}$ 的锁以及相应的钥匙。

一个长 7 cm、宽 8 cm 的锁以及相应的钥匙

表示上边缘的序列为 $[2, 1, 3, 2, 3, 2, 3]$，表示下边缘的序列为 $[3, 4, 2, 3, 2, 3, 4]$。Mirko 注意到有些钥匙可以打开多个锁。制作钥匙是一项繁琐的工作，因此 Mirko 请你帮他计算出，在能够打开所有锁的前提下，他最少需要制作多少把不同的钥匙。

输入格式

输入的第一行包含三个整数 $W$（$1 \le W \le 10^8$），表示所有锁的宽度；$L$（$1 \le L \le 1000$），表示所有锁的长度；以及 $N$（$1 \le N \le 100$），表示不同锁的数量。

接下来的 $2N$ 行描述所有的锁。每行包含恰好 $L$ 个小于 $W$ 的非负整数。每两行描述一个锁：其中第一行描述上边缘，第二行描述下边缘。在所有锁上，两边缘之间始终至少留有 $1\text{ cm}$ 的空白空间。

输出格式

输出唯一的一行，包含一个整数，表示 Mirko 最少需要制作的不同钥匙数量。

样例

输入 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

输入 2

8 4 4
3 3 3 3
3 3 3 3
2 2 2 2
4 4 4 4
1 2 3 4
4 3 2 1
1 1 1 1
5 5 5 5

输出 2

2

输入 3

100000000 2 2
88888888 88888888
4 4
4 4
88888888 88888888

输出 3

1