Cows and Packages Pickup

Farmer John distributes cows and packages along a number line in a peculiar way. He first chooses an integer \(M\) (\(1\le M\le 10^{18}\)). Then he chooses \(N\) intervals \([L_i,R_i]\) (with \(1\le L_i\le R_i\le 10^{18}\) and \(R_i-L_i\) a multiple of \(M\)) in which he places cows at positions \(L_i, L_i+M, L_i+2M,\dots,R_i\). Similarly, he chooses \(P\) intervals \([A_j,B_j]\) (with \(1\le A_j\le B_j\le 10^{18}\) and \(B_j-A_j\) a multiple of \(M\)) in which he places packages at positions \(A_j, A_j+M, A_j+2M,\dots,B_j\>.

Once the cows and packages are distributed, Farmer John wants them all collected. The rules are as follows: every second, he can command a single cow to move one unit to the left or right. When a cow reaches a position containing a package, it picks it up automatically. Note that cows are distinct and each cow can be used to pick up one package by moving directly from its starting position to the package. Although a cow is capable of collecting multiple packages, assigning one cow per package if possible is optimal since the total time is the sum of all individual moves (one unit move per second overall, not concurrently).

Thus, the problem reduces to assigning each package to a distinct cow such that the total moving distance \(\sum |\text{package position} - \text{cow position}|\) is minimized. After scaling by \(M\) (since all positions occur at arithmetic intervals with difference \(M\)), both cow positions and package positions become sorted sequences of integers. In an optimal matching of two sequences in one dimension, the cows and packages should be paired in order. If the set of cows (denoted as \(X\)) is larger than the set of packages (denoted as \(Y\)), then the optimal solution is to choose a consecutive subsequence of \(X\) of the same size as \(Y\) which minimizes \(\sum_{i=1}^{|Y|} |Y_i - X_{i}|\) (after appropriate alignment).

Your task is to calculate the minimum total time (in seconds) required for the cows to pick up all the packages, i.e. the minimum sum of moves needed if each package is collected by a distinct cow.

Note: The time limit for this problem is 4 seconds, twice the default.

inputFormat

The input is given in the following format:

M
N
L_1 R_1
L_2 R_2
... (N lines total)
P
A_1 B_1
A_2 B_2
... (P lines total)

Here, \(M\) is the step used for distributing cows and packages. For each cow interval \([L_i,R_i]\), cows are placed at positions \(L_i, L_i+M, L_i+2M, \dots, R_i\); it is guaranteed that \(R_i-L_i\) is a multiple of \(M\). Similarly for packages.

outputFormat

Output a single integer: the minimum total time (in seconds) required for the cows to pick up all packages.

sample

1
1
3 5
1
2 2

1