Problems
Farmer John has distributed cows and packages in a weird pattern across the number line using the following process:
Farmer John chooses a number M (1 ≤ M ≤ 10^18). Farmer John chooses N (1 ≤ N ≤ 2⋅10^4) intervals [Li, Ri] to distribute cows in (1 ≤ Li ≤ Ri ≤ 10^18). He then places cows at locations Li, Li + M, Li + 2M, …, Ri. It is guaranteed that Ri - Li is a multiple of M. Farmer John chooses P (1 ≤ P ≤ 2⋅10^4) intervals [Ai, Bi] to distribute packages in (1 ≤ Ai ≤ Bi ≤ 10^18). He then places packages at locations Ai, Ai + M, Ai + 2M, …, Bi. It is guaranteed that Bi - Ai is a multiple of M. 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.
Input
The first line contains M, N, and P. The next N lines each contain two integers Li and Ri. The next P lines each contain two integers Ai and Bi.
Output
Output a single integer, representing the minimum amount of time it can take the cows to pick up all the packages.
Example #1
100 3 7
10 10
20 20
30 30
7 7
11 11
13 13
17 17
24 24
26 26
33 33
22
In the above test case, suppose the cows and packages are numbered from left to right. Farmer John can follow this procedure to pick up the packages in 22 seconds: Issue 3 lefts to cow 1 so that it picks up package 1. Issue 3 rights to cow 3 so that it picks up package 7. Issue 4 rights to cow 2 so that it picks up package 5. Issue 10 rights to cow 1 so that it picks up packages 2, 3, and 4. Issue 2 rights to cow 2 so that it picks up package 6.
Example #2
2 1 1
1 5
2 6
3
There are three cows and three packages. Farmer John can issue one right to each cow.
You must sign in to write code.