**Замечание: время на тест в этой задаче 4 сек, в два раза больше, чем по умолчанию.**
Фермер Джон распределил коров и пакеты по странной схеме на числовой оси, используя следующий процесс:
- ФД выбрал число \(M\) (\(1 \le M \le 10^{18}\)).
- ФД выбрал \(N\) (\(1 \le N \le 2 \cdot 10^4)\) интервалов \([L_i, R_i]\)
чтобы распределить коров (\(1 \le L_i \le R_i \le 10^{18}\)).
Затем он разместил коров в позициях \(L_i, L_i + M, L_i + 2M, \ldots, R_i\).
Гарантируется, что \(R_i - L_i\) кратно \(M\).
- ФД выбирает \(P\) (\(1 \le P \le 2 \cdot 10^4)\) интервалов \([A_i, B_i]\)
чтоб распределить пакеты (\(1 \le A_i \le B_i \le 10^{18}\)). Затем
он размещает пакеты в позициях \(A_i, A_i + M, A_i + 2M, \ldots, B_i\).
Гарантируется, что \(B_i - A_i\) кратно \(M\).
Поле распределения коров и пакетов, ФД хочет увидеть сколько времени требуется коровам,
чтобы забрать пакеты. Каждую секунду ФД может дать команду одной корове двинуться
на одну единицу влево или вправо от текущей позиции. Если корова попадает в позицию,
где размещён пакет, она его забирает. ФД хочет узнать минимальное количество секунд,
которое потребуется коровам чтобы собрать все пакеты.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит \(M\), \(N\), \(P\).
Каждая из последующих \(N\) строк содержит два целых числа \(L_i\) и \(R_i\).
Каждая из последующих \(P\) строк содержит два целых числа \(A_i\) и \(B_i\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Выведите одно целое число, представляющее минимальное количество времени,
которое потребуется коровам, собрать все пакеты, если в каждую секунду он
может передвинуть одну любую корову влево или вправо на единицу.
Примеры
| № | Входные данные | Выходные данные |
|
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
|