CF729C.Road to Cinema

Vasya is currently at a car rental service, and he wants to reach cinema. The film he has bought a ticket for starts in t minutes. There is a straight road of length s from the service to the cinema. Let's introduce a coordinate system so that the car rental service is at the point 0, and the cinema is at the point s.

There are k gas stations along the road, and at each of them you can fill a car with any amount of fuel for free! Consider that this operation doesn't take any time, i.e. is carried out instantly.

There are n cars in the rental service, i-th of them is characterized with two integers c__i and v__i — the price of this car rent and the capacity of its fuel tank in liters. It's not allowed to fuel a car with more fuel than its tank capacity v__i. All cars are completely fueled at the car rental service.

Each of the cars can be driven in one of two speed modes: normal or accelerated. In the normal mode a car covers 1 kilometer in 2 minutes, and consumes 1 liter of fuel. In the accelerated mode a car covers 1 kilometer in 1 minutes, but consumes 2 liters of fuel. The driving mode can be changed at any moment and any number of times.

Your task is to choose a car with minimum price such that Vasya can reach the cinema before the show starts, i.e. not later than in t minutes. Assume that all cars are completely fueled initially.

瓦西娅目前在一家汽车租赁服务处，他想前往电影院。他已购票的电影将在 $t$ 分钟后开始放映。从租车服务处到电影院之间有一条长度为 $s$ 的笔直道路。我们建立一个坐标系，使得租车服务处位于坐标 $0$ 处，而电影院位于坐标 $s$ 处。

沿该道路共有 $k$ 个加油站，且在每个加油站均可免费为汽车加任意量的燃油！假设加油操作不耗时间，即瞬间完成。

租车服务处共有 $n$ 辆汽车，其中第 $i$ 辆汽车由两个整数 $c_i$ 和 $v_i$ 表征——分别为该车的租赁价格（单位：元）及其油箱容量（单位：升）。不允许为汽车添加超过其油箱容量 $v_i$ 的燃油。所有汽车在租车服务处出发时均已加满油。

每辆汽车均可在两种行驶模式中任选其一：普通模式或加速模式。在普通模式下，汽车每行驶 1 千米需耗时 2 分钟，并消耗 1 升燃油；在加速模式下，汽车每行驶 1 千米仅需耗时 1 分钟，但消耗 2 升燃油。行驶模式可在任意时刻、任意次数地切换。

你的任务是选择一辆价格最低的汽车，使得瓦西娅能在电影开始前（即不超过 $t$ 分钟内）抵达电影院。假设所有汽车初始时均已加满油。

The first line contains four positive integers n, k, s and t (1 ≤ n ≤ 2·105, 1 ≤ k ≤ 2·105, 2 ≤ s ≤ 109, 1 ≤ t ≤ 2·109) — the number of cars at the car rental service, the number of gas stations along the road, the length of the road and the time in which the film starts.

Each of the next n lines contains two positive integers c__i and v__i (1 ≤ c__i, v__i ≤ 109) — the price of the i-th car and its fuel tank capacity.

The next line contains k distinct integers _g_1, _g_2, ..., g__k (1 ≤ g__i ≤ s - 1) — the positions of the gas stations on the road in arbitrary order.

第一行包含四个正整数 $n$、$k$、$s$ 和 $t$（$1 \le n \le 2\cdot10^5$，$1 \le k \le 2\cdot10^5$，$2 \le s \le 10^9$，$1 \le t \le 2\cdot10^9$）——分别表示汽车租赁服务处的汽车数量、公路上的加油站数量、公路长度以及电影开始的时间。

接下来的 $n$ 行，每行包含两个正整数 $c_i$ 和 $v_i$（$1 \le c_i,\,v_i \le 10^9$）——分别表示第 $i$ 辆汽车的价格及其油箱容量。

下一行包含 $k$ 个互不相同的整数 $g_1,\,g_2,\,...,\,g_k$（$1 \le g_i \le s - 1$）——以任意顺序给出公路上各加油站的位置。

Print the minimum rent price of an appropriate car, i.e. such car that Vasya will be able to reach the cinema before the film starts (not later than in t minutes). If there is no appropriate car, print -1.

输出合适汽车的最低租金价格，即瓦西娅能在电影开始前（不晚于 t 分钟）抵达电影院所租用的汽车。若不存在合适的汽车，则输出 -1。

In the first sample, Vasya can reach the cinema in time using the first or the third cars, but it would be cheaper to choose the first one. Its price is equal to 10, and the capacity of its fuel tank is 8. Then Vasya can drive to the first gas station in the accelerated mode in 3 minutes, spending 6 liters of fuel. After that he can full the tank and cover 2 kilometers in the normal mode in 4 minutes, spending 2 liters of fuel. Finally, he drives in the accelerated mode covering the remaining 3 kilometers in 3 minutes and spending 6 liters of fuel.

在第一个样例中，瓦西娅可以使用第一辆或第三辆车及时到达电影院，但选择第一辆车更便宜。它的价格为 $10$，油箱容量为 $8$。接着，瓦西娅可以以加速模式行驶至第一个加油站，耗时 $3$ 分钟，消耗 $6$ 升燃油；之后他可将油箱加满，并以正常模式行驶 $2$ 千米，耗时 $4$ 分钟，消耗 $2$ 升燃油；最后，他以加速模式行驶剩余的 $3$ 千米，耗时 $3$ 分钟，消耗 $6$ 升燃油。