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.

#8423 upload 2 done 1 how_to_reg 1

Package Pickup timer 4s memory 1024MB

#8423

Package Pickup 4s 1024MB