E. Чайный магазин
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вчера Саша решил открыть чайный магазин на улице, где он живёт. У него есть $$$m$$$ вариантов расположения магазина. Вариант под номером $$$i$$$ задаётся натуральным числом $$$x_i$$$ — расстоянием от начала улицы.

На улице живёт $$$n$$$ человек. Человек под номером $$$j$$$ живёт на расстоянии $$$y_j$$$ от начала улицы. Саша узнал, что $$$j$$$-й человек купит одну чайную упаковку, если сумма расстояния, которое ему нужно пройти от дома до магазина, и цены чайной упаковки не будут превышать число $$$a_j$$$. То есть, если Саша выберет помещение под номером $$$i$$$ и установит цену на чай равную числу $$$c$$$, то $$$j$$$-й человек обязательно купит ровно одну упаковку чая, если $$$|x_i - y_j| + c \le a_j$$$. Человек не может купить больше одной упаковки.

Саша уже изготовил $$$k$$$ упаковок и собирается всё продать. Помогите ему установить максимальную цену упаковки чая, чтобы он смог продать все $$$k$$$ упаковок без остатка. Либо выведите $$$-1$$$, если это невозможно.

Входные данные

В первой строке дано три числа $$$n$$$, $$$m$$$, $$$k$$$ $$$(1 \le n, m, k \le 10^5)$$$ — количество людей, которые живут на улице (в своих домах, разумеется), количество вариантов площадок для расположения магазина и количество готовых упаковок чая соответственно.

В следующих $$$n$$$ строках даны $$$n$$$ пар чисел. В $$$j$$$-ой строке находятся два числа $$$y_j$$$ и $$$a_j$$$ $$$(1 \le y_j, a_j \le 10^9)$$$.

И в последней строке даны $$$m$$$ чисел $$$x_1, x_2, x_3, \dots, x_m$$$ $$$(1 \le x_i \le 10^9)$$$, где $$$x_i$$$ — расстояние $$$i$$$-й площадки для расположения магазина.

Выходные данные

Выведите, какую максимальную цену одной упаковки чая нужно установить Саше, чтобы он смог продать все $$$k$$$ упаковок, или $$$-1$$$, если это невозможно.

Система оценки

Тесты к этой задаче состоят из нескольких групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов всех необходимых групп.

ГруппаБаллыДополнительныеНеобх. группыКомментарий
ограничения
00––Тесты из условия.
113$$$1 \le n, m, a_i \le 100$$$–
219$$$1 \le n, m \le 1000$$$1
333$$$1 \le n \le 10^5, m = 1$$$–Существует только одна
площадка для магазина
435–1, 2, 3
Примеры
Входные данные
3 4 2
1 5
5 3
2 6
1 2 3 4
Выходные данные
5
Входные данные
4 3 4
1 2
4 1
6 3
7 3
3 6 9
Выходные данные
-1
Входные данные
5 1 3
2 1
3 2
5 3
7 4
8 5
3
Выходные данные
0