問題文

$2$ 行 $L$ 列のマス目があります。 上から $i$ 行目 $(i\\in\\lbrace1,2\\rbrace)$、左から $j$ 列目 $(1\\leq j\\leq L)$のマス目を $(i,j)$ で表します。 $(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$ の列 $((v _ {1,1},l _ {1,1}),\\ldots,(v _ {1,N _ 1},l _ {1,N _ 1}))$ と長さ $N _ 2$ の列 $((v _ {2,1},l _ {2,1}),\\ldots,(v _ {2,N _ 2},l _ {2,N _ 2}))$ として与えられます。

ここで、列 $A$ の連長圧縮とは、$A$ の要素 $v _ i$ と正整数 $l _ i$ の組 $(v _ i,l _ 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$ 行で出力せよ。

入力例 1

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

出力例 1

4

マス目は以下の図のようになっています。

$x _ {1,j}=x _ {2,j}$ となるような整数 $j$ は、$j=1,2,5,8$ の $4$ つなので、出力すべき値は $4$ です。

入力例 2

10000000000 1 1
1 10000000000
1 10000000000

出力例 2

10000000000

答えが $32\\operatorname{bit}$ 整数に収まらない場合があることに注意してください。

入力例 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