分数: 500 点
问题陈述
我们有一个网格 2 行和 L 列。 让 (i,j) 表示 i从顶部算起的第行 (i\in\lbrace1,2\rbrace) 和 j左起第 列 (1\leq j\leq L). (i,j) 有一个整数 x _ {i,j} 。
查找整数的个数 j 这样 x _ {1,j}=x _ {2,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 of A 和一个正整数 l _ i 获得如下。
- 分裂 A 每对不同的相邻元素之间。
- 对于每个序列 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
网格如下所示。

我们有四个整数 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