#abc294e. [abc294_e]2xN Grid

[abc294_e]2xN Grid

Problem Statement

We have a grid with 22 rows and LL columns. Let (i,j)(i,j) denote the square at the ii-th row from the top (iinlbrace1,2rbrace)(i\\in\\lbrace1,2\\rbrace) and jj-th column from the left (1leqjleqL)(1\\leq j\\leq L). (i,j)(i,j) has an integer xi,jx _ {i,j} written on it.

Find the number of integers jj such that x1,j=x2,jx _ {1,j}=x _ {2,j}.

Here, the description of xi,jx _ {i,j} is given to you as the run-length compressions of (x1,1,x1,2,ldots,x1,L)(x _ {1,1},x _ {1,2},\\ldots,x _ {1,L}) and (x2,1,x2,2,ldots,x2,L)(x _ {2,1},x _ {2,2},\\ldots,x _ {2,L}) into sequences of lengths N1N _ 1 and N2N _ 2, respectively: ((v1,1,l1,1),ldots,(v1,N1,l1,N1))((v _ {1,1},l _ {1,1}),\\ldots,(v _ {1,N _ 1},l _ {1,N _ 1})) and ((v2,1,l2,1),ldots,(v2,N2,l2,N2))((v _ {2,1},l _ {2,1}),\\ldots,(v _ {2,N _ 2},l _ {2,N _ 2})).

Here, the run-length compression of a sequence AA is a sequence of pairs (vi,li)(v _ i,l _ i) of an element viv _ i of AA and a positive integer lil _ i obtained as follows.

  1. Split AA between each pair of different adjacent elements.
  2. For each sequence B1,B2,ldots,BkB _ 1,B _ 2,\\ldots,B _ k after the split, let viv _ i be the element of BiB _ i and lil _ i be the length of BiB _ i.

Constraints

  • 1leqLleq10121\\leq L\\leq 10 ^ {12}
  • 1leqN1,N2leq1051\\leq N _ 1,N _ 2\\leq 10 ^ 5
  • 1leqvi,jleq109(iinlbrace1,2rbrace,1leqjleqNi)1\\leq v _ {i,j}\\leq 10 ^ 9\\ (i\\in\\lbrace1,2\\rbrace,1\\leq j\\leq N _ i)
  • 1leqli,jleqL(iinlbrace1,2rbrace,1leqjleqNi)1\\leq l _ {i,j}\\leq L\\ (i\\in\\lbrace1,2\\rbrace,1\\leq j\\leq N _ i)
  • vi,jneqvi,j+1(iinlbrace1,2rbrace,1leqjltNi)v _ {i,j}\\neq v _ {i,j+1}\\ (i\\in\\lbrace1,2\\rbrace,1\\leq j\\lt N _ i)
  • li,1+li,2+cdots+li,Ni=L(iinlbrace1,2rbrace)l _ {i,1}+l _ {i,2}+\\cdots+l _ {i,N _ i}=L\\ (i\\in\\lbrace1,2\\rbrace)
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

LL N1N _ 1 N2N _ 2 v1,1v _ {1,1} l1,1l _ {1,1} v1,2v _ {1,2} l1,2l _ {1,2} vdots\\vdots v1,N1v _ {1,N _ 1} l1,N1l _ {1,N _ 1} v2,1v _ {2,1} l2,1l _ {2,1} v2,2v _ {2,2} l2,2l _ {2,2} vdots\\vdots v2,N2v _ {2,N _ 2} l2,N2l _ {2,N _ 2}

Output

Print a single line containing the answer.


Sample Input 1

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

Sample Output 1

The grid is shown below.

We have four integers jj such that x1,j=x2,jx _ {1,j}=x _ {2,j}: j=1,2,5,8j=1,2,5,8. Thus, you should print 44.


Sample Input 2

10000000000 1 1
1 10000000000
1 10000000000

Sample Output 2

10000000000

Note that the answer may not fit into a 3232-bit integer.


Sample Input 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

Sample Output 3

380