406735: GYM102512 D Equality

Kotaro and Akane like to chat with each other on LINE. However, they have found that replying to messages instantly every time can be too tiresome. They still do not want the other person to feel ignored though, so they came up with the following plan:

Firstly, they agree on a positive integer $$$T$$$. Every day, Kotaro will send a message at time $$$T$$$. Then, after every $$$T$$$ units of time, the person who last received a message will reply (hence Kotaro will send a message at time $$$T, 3T, 5T, ...$$$ and Akane will send a message at time $$$2T, 4T, 6T, ...$$$).

However, there are $$$N$$$ units of time per day and they cannot be online all the time. Specifically, Kotaro will be active during time $$$[a_1,b_1], [a_2,b_2],..., [a_X,b_X]$$$, while Akane will be active during time $$$[c_1,d_1], [c_2,d_2],..., [c_Y,d_Y]$$$ (here $$$[L,R]$$$ denotes the interval of time from time $$$L$$$ to time $$$R$$$ inclusive).

They want to choose the value of $$$T$$$ to ensure that they will be online to send the messages on time. How many values of $$$T$$$ from $$$1$$$ to $$$N$$$ can they choose?

The first line of input contains a single integer $$$N$$$ ($$$1 \le N \le 10^{9}$$$).

The next line of input contains a single integer $$$X$$$ ($$$1 \le X \le 300$$$), denoting the number of intervals of time when Kotaro will be online.

The next $$$X$$$ lines of input contain two space-separated integers each, denoting $$$a_i, b_i$$$ ($$$1 \le a_i \le b_i \le N$$$). It is guaranteed that $$$a_{i+1} > b_{i} + 1$$$ holds for all $$$1 \le i \le X - 1$$$.

The next line of input contains a single integer $$$Y$$$ ($$$1 \le Y \le 300$$$), denoting the number of intervals of time when Akane will be online.

The next $$$Y$$$ lines of input contain two space-separated integers each, denoting $$$c_i, d_i$$$ ($$$1 \le c_i \le d_i \le N$$$). It is guaranteed that $$$c_{i+1} > d_{i} + 1$$$ holds for all $$$1 \le i \le Y - 1$$$.

Output a single integer, the number of positive integers $$$T$$$ that Kotaro and Akane can choose.

Subtask 1 (9 points): $$$N \le 10^{6}$$$

Subtask 2 (40 points): $$$X = Y, a_{i} = c_{i}, b_{i} = d_{i}$$$ for all $$$1 \le i \le X$$$.

Subtask 3 (51 points): No additional constraints

10
2
2 4
6 9
3
1 3
5 7
9 10

5

10000000
1
4092001 5033941
2
206 314
1214 10000000

941941

For the first sample, they can choose the values $$$T = 3, 6, 7, 8, 9$$$.

If $$$T = 6, 7, 8, 9$$$ is chosen, then only one message will be sent per day and Kotaro is active at the time.

If $$$T = 3$$$ is chosen, then Kotaro sends a message at time $$$3, 9$$$ while Akane sends a message at time $$$6$$$, and they are indeed active during these times.

Note that $$$T = 2$$$ fails because Akane is not active at time $$$4$$$, while $$$T = 5$$$ fails because Kotaro is not active at time $$$5$$$.