2xN 网格

题目描述

有一个 $2$ 行 $L$ 列的网格。设 $(i,j)$ 表示从上数第 $i$ 行 $(i\in\lbrace 1,2\rbrace)$、从左数第 $j$ 列 $(1 \le j \le L)$ 的格子。$(i,j)$ 上写有整数 $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$ 是 $A$ 中的元素，$l _ i$ 是正整数。

在每对相邻且不同的元素之间把 $A$ 切开。

对切分后得到的每个序列 $B _ 1,B _ 2,\ldots,B _ k$，令 $v _ i$ 为 $B _ i$ 中的元素，$l _ i$ 为 $B _ i$ 的长度。

输入格式

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

$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}$

输出格式

输出一行，包含答案。

样例

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

4

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

10000000000 1 1
1 10000000000
1 10000000000

10000000000

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

380

数据范围

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

提示

注意，答案可能超出 32 位整数的范围。