CF729C Road to Cinema

Vasya 目前在一家汽车租赁服务点，他希望前往电影院。他购买的电影票将在 $ t $ 分钟后开场。有一条长度为 $ s $ 的直路从服务点通向电影院。我们引入一个坐标系，使得汽车租赁服务点在点 $ 0 $，电影院在点 $ s $。 路上有 $ k $ 个加油站，在每个加油站处可以免费为汽车加任意数量的燃油！假设这个操作不需要时间，即为瞬时完成。 租赁服务点有 $ n $ 辆汽车，第 $ i $ 辆车有两个整数参数 $ c_{i} $ 和 $ v_{i} $——分别为该车的租赁价格和油箱容量（升）。不能为汽车加超过其油箱容量 $ v_{i} $ 的油。所有汽车在租赁服务点均已加满油箱。 每辆车可以以两种速度模式行驶：普通模式或加速模式。普通模式下，汽车每行驶 $ 1 $ 公里需要 $ 2 $ 分钟，消耗 $ 1 $ 升油。加速模式下，每行驶 $ 1 $ 公里需 $ 1 $ 分钟，但消耗 $ 2 $ 升油。驾驶模式可以在任意时刻、任意次数切换。 你的任务是选择一辆价格最便宜的汽车，使 Vasya 能在电影开场前及时到达电影院，即在不超过 $ t $ 分钟内。假定所有汽车起始时油箱都已加满。

第一行包含四个正整数 $ n $、$ k $、$ s $ 和 $ t $（$ 1\le n\le 2·10^{5} $，$ 1\le k\le 2·10^{5} $，$ 2\le s\le 10^{9} $，$ 1\le t\le 2·10^{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 $），表示各加油站在道路上的位置，顺序任意。

输出一辆合适汽车的最小租赁价格，即 Vasya 能在电影开场前到达电影院（不超过 $ t $ 分钟）的汽车中的最低价格。如果不存在合适的汽车，则输出 $ -1 $。

在第一个样例中，Vasya 可以使用第一辆或第三辆汽车按时到达电影院，但选择第一辆会更便宜。其租赁价格是 $ 10 $，油箱容量为 $ 8 $。Vasya 可以在加速模式下以 $ 3 $ 分钟驶达第一个加油站，耗油 $ 6 $ 升。之后可加满油，再用普通模式行驶 $ 2 $ 公里，耗时 $ 4 $ 分钟、耗油 $ 2 $ 升。最后，使用加速模式行驶剩余 $ 3 $ 公里，用时 $ 3 $ 分钟、耗油 $ 6 $ 升。 由 ChatGPT 5 翻译