У Фермера Джона длинная ферма вдоль скоростной дороги, которую можно рассматривать как числовую прямую. Вдоль фермы имеется k травяных пастбищ; i-ое пастбище расположено в позиции p[i]
и имеет величину вкусности t[i]
. Фермер Нхой уже расположил свои m коров в позициях f[1]
..f[m]
. Все k + m этих чисел различны и находятся в интервале [0, 10^9
].
ФД хочет выбрать n (не обязательно в целых числах) для размещения своих коров. Эти числа должны отличаться от позиций занимаемых коровами ФН, но они могут находится в позициях травяных пастбищ.
Корова какого фермера находится ближе к травяному пастбищу, тот и объявляется собственником этого пастбища. Если коровы обоих фремеров находятся на одинаковом расстоянии от пастбища, то оно объявляется принадлежащим ФН.
По заданным позициям коров ФН и вкусностям пастбищ определите максимальную вкусность суммарную, которой может добиться ФД оптимальным размещением своих коров.
Первая строка содержит k (1 ≤ k ≤ 2 * 10^5
), m (1 ≤ m ≤ 2 * 10^5
), n (1 ≤ n ≤ 2 * 10^5
).
Каждая из последующих k строк содержит два целых числа p[i]
и t[i]
(0 ≤ t[i]
≤ 10^9
).
Каждая из последующих m строк содержит f[i]
.
Выведите одно целое число - максимальную суммарную вкусность. Заметим, что ответ может превысить 32-битное целое число, поэтому нужно использовать 64-битное, например long long в С++.
Если ФД разместит своих коров в позициях 11.5 и 8, он достигнет суммарной вкусности 10 + 12 + 14 = 36.