Vasya 目前在汽车租赁服务处,他想去电影院。他买了票的电影在 t 分钟后开始。从服务处到电影院有一条长度为 s 的笔直道路。我们引入一个坐标系,让租车服务在点0,电影院在点s。
沿路有k个加油站,每个加油站都可以免费给一辆车加任意量的油!考虑到此操作不需要任何时间,即立即执行。
租赁服务中有 n 辆汽车,其中第 i 辆汽车的特征是两个整数 ci 和 vi ——该汽车租赁的价格及其油箱容量(以升为单位)。不允许为汽车添加超过其油箱容量 vi 的燃油。所有车辆均在汽车租赁服务处加满油。
每辆车都可以以两种速度模式之一驾驶:正常或加速。在正常模式下,汽车2分钟行驶1公里,消耗1升燃油。在加速模式下,汽车在 1 分钟内行驶 1 公里,但消耗 2 升燃油。驾驶模式可以随时、任意次数地改变。
你的任务是选择一辆价格最低的汽车,以便 Vasya 可以在演出开始前(即不晚于 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) - 加油站在道路上的位置(按任意顺序排列)。
输出
打印适当汽车的最低租金价格,即 Vasya 能够在电影开始前(不晚于 t 分钟)到达电影院的汽车。如果没有合适的汽车,则打印-1。
示例
输入 #1
3 1 8 10 10 8 5 7 11 9 3
输出 #1
10
输入 #2
2 2 10 18 10 4 20 6 5 3
输出 #2
20
注意
在第一个示例中,Vasya 可以使用第一辆车或第三辆车及时到达电影院,但选择第一辆车会更便宜。它的价格等于10,油箱容量为8。然后Vasya可以在3分钟内以加速模式行驶到第一个加油站,花费6升燃油。之后,他可以在4分钟内加满油箱并在正常模式下行驶2公里,消耗2升燃油。最后,他以加速模式行驶,在 3 分钟内行驶完剩余的 3 公里,消耗了 6 升燃油。