У Фермера Джона длинная ферма вдоль скоростной дороги, которую можно рассматривать
как числовую прямую. Вдоль фермы имеется \(K\) травяных пастбищ \(1 \leq K \leq 2\cdot 10^5\));
\(i\)-ое пастбище расположено в позиции \(p_i\) и имеет величину вкусности \(t_i\) (\(0\le t_i\le 10^9\)).
Фермер Нхой уже расположил свои \(M\) коров (\(1 \leq M \leq 2\cdot 10^5\)) в позициях
\(f_1 \ldots f_M\). Все \(K+M\) этих чисел различны и находятся в интервале \([0,10^9]\).
ФД хочет выбрать \(N\) (\(1\le N\le 2\cdot 10^5\)) (не обязательно в целых числах)
для размещения своих коров. Эти числа должны отличаться от позиций занимаемых коровами ФН,
но они могут находится в позициях травяных пастбищ.
Корова какого фермера находится ближе к травяному пастбищу, тот и объявляется
собственником этого пастбища. Если коровы обоих фремеров находятся на одинаковом
расстоянии от пастбища, то оно объявляется принадлежащим ФН.
По заданным позициям коров ФН и вкусностям пастбищ определите максимальную
вкусность суммарную, которой может добиться ФД оптимальным размещением своих коров.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит
\(K\),
\(M\),
\(N\).
Каждая из последующих \(K\) строк содержит два разделённых пробелом целых числа
\(p_i\) и \(t_i\).
Каждая из последующих \(M\) строк содержит \(f_i\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Одно целое число, максимальную суммарную вкусность. заметим, что ответ может
превысить 32-битное целое число, поэтому нужно использовать 64-битное, например
long long в С++.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 5 2
0 4
4 6
8 10
10 8
12 12
13 14
2
3
5
7
11
|
36
|