Package Pickup

문제

Farmer John has distributed cows and packages in a weird pattern across the number line using the following process:

• Farmer John chooses a number $MM$ ($1\le M\le {10}^{18}1\; \backslash le\; M\; \backslash le\; 10^\{18\}$).
• Farmer John chooses $NN$ ($1\le N\le 2\cdot {10}^4)1\; \backslash le\; N\; \backslash le\; 2\; \backslash cdot\; 10^4)$ intervals $[L_i,R_i][L\_i,\; R\_i]$ to distribute cows in ($1\le L_i\le R_i\le {10}^{18}1\; \backslash le\; L\_i\; \backslash le\; R\_i\; \backslash le\; 10^\{18\}$). He then places cows at locations $L_i,L_i+M,L_i+2M,\dots ,R_{i}L\_i,\; L\_i\; +\; M,\; L\_i\; +\; 2M,\; \backslash ldots,\; R\_i$. It is guaranteed that $R_i-L_{i}R\_i\; -\; L\_i$ is a multiple of $MM$.
• Farmer John chooses $PP$ ($1\le P\le 2\cdot {10}^4)1\; \backslash le\; P\; \backslash le\; 2\; \backslash cdot\; 10^4)$ intervals $[A_i,B_i][A\_i,\; B\_i]$ to distribute packages in ($1\le A_i\le B_i\le {10}^{18}1\; \backslash le\; A\_i\; \backslash le\; B\_i\; \backslash le\; 10^\{18\}$). He then places packages at locations $A_i,A_i+M,A_i+2M,\dots ,B_{i}A\_i,\; A\_i\; +\; M,\; A\_i\; +\; 2M,\; \backslash ldots,\; B\_i$. It is guaranteed that $B_i-A_{i}B\_i\; -\; A\_i$ is a multiple of $MM$.

Once the cows and packages are distributed, Farmer John wants to see how long it takes the cows to pick up the packages. Every second, Farmer John can issue a command to a single cow to move one unit left or right of their current position with his handy walkie talkie. If a cow travels to the position where a package is located, they are able to pick it up. Farmer John wants to know the minimum time in seconds that it would take the cows to pick up every package.

입력

The first line contains $MM$, $NN$, and $PP$.

The next $NN$ lines each contain two integers $L_{i}L\_i$ and $R_{i}R\_i$.

The next $PP$ lines each contain two integers $A_{i}A\_i$ and $B_{i}B\_i$.

출력

Output a single integer, representing the minimum amount of time it can take the cows to pick up all the packages, given that every second, he can issue a single left/right command to a single cow.

100 3 7
10 10
20 20
30 30
7 7
11 11
13 13
17 17
24 24
26 26
33 33

22

2 1 1
1 5
2 6

3