← 返回题目列表

Codeforces · 729/C

C. 电影院之路

中文机器翻译题面 查看原题

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 升燃油。