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

Вася находится в центре проката машин и хочет как можно скорее добраться до кинотеатра. Сеанс, на который он уже купил билет, начнётся через t минут. Считайте, что есть прямая дорога от центра проката машин до кинотеатра длиной s километров. Введём систему координат так, что центр проката машин находится в точке 0, а кинотеатр находится в точке s.

Известно, что по пути от центра проката машин до кинотеатра есть k заправочных станций, причём на всех можно заливать неограниченное количество топлива совершенно бесплатно! Считайте, что операция залива топлива осуществляется мгновенно.

В центре проката есть n машин, i-я из которых характеризуется двумя числами ci и vi — стоимостью аренды машины и вместимостью её бака. Таким образом, на заправке нельзя заливать в машину топлива больше вместимости её бака vi. В центре проката все машины изначально полностью заправлены.

Каждая из машин может ехать в одном из двух скоростных режимов: обычном и ускоренном. В обычном режиме машина проезжает 1 километр за 2 минуты, при этом тратит на это 1 литр топлива. В ускоренном режиме машина проезжает 1 километр за 1 минуту, при этом тратит на это 2 литра топлива. Режим может быть изменён в любой момент. Изменять режим разрешается неограниченное количество раз.

Перед вами стоит задача выбрать машину с минимальной стоимостью аренды, на которой Вася успеет добраться до кинотеатра до начала своего сеанса, то есть не позднее, чем через t минут. Считайте, что в центре проката все машины изначально полностью заправлены.

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

В первой строке записаны четыре целых положительных числа n, k, s и t (1 ≤ n ≤ 2·105, 1 ≤ k ≤ 2·105, 2 ≤ s ≤ 109, 1 ≤ t ≤ 2·109) — количество машин в центре проката, количество заправок на пути до кинотеатра, позиция кинотеатра и время, оставшееся до начала сеанса.

В следующих n строках следуют по два целых положительных числа ci и vi (1 ≤ ci, vi ≤ 109) — стоимость аренды i-й машины и объём её топливного бака.

В следующей строке следуют k различных целых чисел g1, g2, ..., gk (1 ≤ gi ≤ s - 1) — позиции заправок на пути до кинотеатра в произвольном порядке.

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

Выведите минимальную стоимость аренды подходящей машины, то есть такой, что Вася успеет добраться до кинотеатра до начала сеанса (не позднее, чем через t минут). Если ни одна из машин не подойдёт Васе, выведите -1.

Примеры
Входные данные
3 1 8 10
10 8
5 7
11 9
3
Выходные данные
10
Входные данные
2 2 10 18
10 4
20 6
5 3
Выходные данные
20
Примечание

В первом примере Вася успеет доехать до кинотеатра вовремя на первой и третьей машине, но выгоднее поехать на первой, стоимость аренды которой равна 10, а объём топливного бака равен 8. Тогда до первой заправки Вася сможет доехать в ускоренном режиме за 3 минуты, потратив на это 6 литров топлива, а затем, заправив полный бак, он сможет проехать 2 километра в обычном режиме за 4 минуты, потратив на это 2 литра бензина. Оставшиеся 3 километра он проедет в ускоренном режиме за 3 минуты, потратив на это 6 литров бензина.