问题陈述

我们有一个 $2$ 行 $L$ 列的网格。用 $(i,j)$ 表示从上方数第 $i$ 行、从左边数第 $j$ 列的方块 $(i\in\lbrace1,2\rbrace)$，上面写着一个整数 $x _ {i,j}$。

找到满足 $x _ {1,j}=x _ {2,j}$ 的整数 $j$ 的个数。

这里，将 $x _ {i,j}$ 的描述作为 $(x _ {1,1},x _ {1,2},\ldots,x _ {1,L})$ 和 $(x _ {2,1},x _ {2,2},\ldots,x _ {2,L})$ 的游程压缩给出：分别是长度 $N _ 1$ 和 $N _ 2$ 的序列 $((v _ {1,1},l _ {1,1}),\ldots,(v _ {1,N _ 1},l _ {1,N _ 1}))$ 和 $((v _ {2,1},l _ {2,1}),\ldots,(v _ {2,N _ 2},l _ {2,N _ 2}))$。

这里，序列 $A$ 的游程压缩是由以下方式得到的一系列对 $(v _ i,l _ i)$：其中 $v _ i$ 是 $B _ i$ 中的元素，$l _ i$ 是 $B _ i$ 的长度。

1. 将 $A$ 在每对不同相邻元素之间拆分。
2. 在拆分后的每个序列 $B _ 1,B _ 2,\ldots,B _ k$ 中，将 $v_i$ 设为 $B _ i$ 的元素，将 $l _ i$ 设为 $B _ i$ 的长度。

约束条件

• $1\leq L\leq 10 ^ {12}$
• $1\leq N _ 1,N _ 2\leq 10 ^ 5$
• $1\leq v _ {i,j}\leq 10 ^ 9\ (i\in\lbrace1,2\rbrace,1\leq j\leq N _ i)$
• $1\leq l _ {i,j}\leq L\ (i\in\lbrace1,2\rbrace,1\leq j\leq N _ i)$
• $v _ {i,j}\neq v _ {i,j+1}\ (i\in\lbrace1,2\rbrace,1\leq j\lt N _ i)$
• $l _ {i,1}+l _ {i,2}+\cdots+l _ {i,N _ i}=L\ (i\in\lbrace1,2\rbrace)$
• 输入中的所有值均为整数。

输入

输入以以下格式从标准输入给出：

$L$ $N _ 1$ $N _ 2$ $v _ {1,1}$ $l _ {1,1}$ $v _ {1,2}$ $l _ {1,2}$ $\vdots$ $v _ {1,N _ 1}$ $l _ {1,N _ 1}$ $v _ {2,1}$ $l _ {2,1}$ $v _ {2,2}$ $l _ {2,2}$ $\vdots$ $v _ {2,N _ 2}$ $l _ {2,N _ 2}$

输出

输出一行，包含答案。

示例输入 1

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

示例输出 1

4

网格如下所示。

我们有 $4$ 个整数 $j$ 满足 $x _ {1,j}=x _ {2,j}$：$j=1,2,5,8$。因此，你应该输出 $4$。

示例输入 2

10000000000 1 1
1 10000000000
1 10000000000

示例输出 2

10000000000

注意，答案可能不适合 $32$ 位整数。

示例输入 3

1000 4 7
19 79
33 463
19 178
33 280
19 255
33 92
34 25
19 96
12 11
19 490
33 31

示例输出 3

380