English · Original
Chinese · Translation
Formal · Original
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.
## Input
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.
## Output
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_.
[samples]
## Note
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.
Vasya 目前位于一家汽车租赁服务点，他希望到达电影院。他购买票的电影将在 #cf_span[t] 分钟后开始。从服务点到电影院有一条长度为 #cf_span[s] 的笔直道路。我们建立一个坐标系，使得汽车租赁服务点位于点 #cf_span[0]，电影院位于点 #cf_span[s]。
道路上有 #cf_span[k] 个加油站，每个加油站都可以免费为汽车加注任意数量的燃油！假设该操作不花费任何时间，即瞬间完成。
租赁服务点共有 #cf_span[n] 辆车，第 #cf_span[i] 辆车由两个整数 #cf_span[ci] 和 #cf_span[vi] 描述——该车的租赁价格及其油箱容量（单位：升）。不允许为汽车加注超过其油箱容量 #cf_span[vi] 的燃油。所有车辆在租赁服务点时均被完全加满油。
每辆车可以以两种模式之一驾驶：普通模式或加速模式。在普通模式下，车辆每行驶 #cf_span[1] 公里需要 #cf_span[2] 分钟，消耗 #cf_span[1] 升燃油；在加速模式下，车辆每行驶 #cf_span[1] 公里需要 #cf_span[1] 分钟，但消耗 #cf_span[2] 升燃油。驾驶模式可以在任意时刻任意次数地切换。
你的任务是选择一辆价格最低的车，使得 Vasya 能在电影开始前到达电影院，即不超过 #cf_span[t] 分钟。假设所有车辆在租赁服务点时均被完全加满油。
第一行包含四个正整数 #cf_span[n], #cf_span[k], #cf_span[s] 和 #cf_span[t]（#cf_span[1 ≤ n ≤ 2·10^5], #cf_span[1 ≤ k ≤ 2·10^5], #cf_span[2 ≤ s ≤ 10^9], #cf_span[1 ≤ t ≤ 2·10^9]）——汽车租赁服务点的车辆数、道路上的加油站数量、道路长度以及电影开始的时间。
接下来的 #cf_span[n] 行，每行包含两个正整数 #cf_span[ci] 和 #cf_span[vi]（#cf_span[1 ≤ ci, vi ≤ 10^9]）——第 #cf_span[i] 辆车的价格及其油箱容量。
下一行包含 #cf_span[k] 个互不相同的整数 #cf_span[g1, g2, ..., gk]（#cf_span[1 ≤ gi ≤ s - 1]）——道路中加油站的位置（顺序任意）。
请输出满足条件的车辆的最低租赁价格，即 Vasya 能在电影开始前（不超过 #cf_span[t] 分钟）到达电影院的车辆。如果没有合适的车辆，请输出 _-1_。
在第一个样例中，Vasya 可以使用第一辆或第三辆车在规定时间内到达电影院，但选择第一辆更便宜。其价格为 #cf_span[10]，油箱容量为 #cf_span[8]。Vasya 可以以加速模式驾驶至第一个加油站，耗时 #cf_span[3] 分钟，消耗 #cf_span[6] 升燃油；之后加满油，以普通模式行驶 #cf_span[2] 公里，耗时 #cf_span[4] 分钟，消耗 #cf_span[2] 升燃油；最后以加速模式行驶剩余的 #cf_span[3] 公里，耗时 #cf_span[3] 分钟，消耗 #cf_span[6] 升燃油。
## Input
第一行包含四个正整数 #cf_span[n], #cf_span[k], #cf_span[s] 和 #cf_span[t]（#cf_span[1 ≤ n ≤ 2·10^5], #cf_span[1 ≤ k ≤ 2·10^5], #cf_span[2 ≤ s ≤ 10^9], #cf_span[1 ≤ t ≤ 2·10^9]）——汽车租赁服务点的车辆数、道路上的加油站数量、道路长度以及电影开始的时间。接下来的 #cf_span[n] 行，每行包含两个正整数 #cf_span[ci] 和 #cf_span[vi]（#cf_span[1 ≤ ci, vi ≤ 10^9]）——第 #cf_span[i] 辆车的价格及其油箱容量。下一行包含 #cf_span[k] 个互不相同的整数 #cf_span[g1, g2, ..., gk]（#cf_span[1 ≤ gi ≤ s - 1]）——道路中加油站的位置（顺序任意）。
## Output
请输出满足条件的车辆的最低租赁价格，即 Vasya 能在电影开始前（不超过 #cf_span[t] 分钟）到达电影院的车辆。如果没有合适的车辆，请输出 _-1_。
[samples]
## Note
在第一个样例中，Vasya 可以使用第一辆或第三辆车在规定时间内到达电影院，但选择第一辆更便宜。其价格为 #cf_span[10]，油箱容量为 #cf_span[8]。Vasya 可以以加速模式驾驶至第一个加油站，耗时 #cf_span[3] 分钟，消耗 #cf_span[6] 升燃油；之后加满油，以普通模式行驶 #cf_span[2] 公里，耗时 #cf_span[4] 分钟，消耗 #cf_span[2] 升燃油；最后以加速模式行驶剩余的 #cf_span[3] 公里，耗时 #cf_span[3] 分钟，消耗 #cf_span[6] 升燃油。
**Definitions**
Let $ n, k, s, t \in \mathbb{Z}^+ $: number of cars, number of gas stations, road length, and deadline in minutes.
Let $ C = \{ (c_i, v_i) \mid i \in \{1, \dots, n\} \} $: set of cars, where $ c_i $ is price and $ v_i $ is fuel tank capacity.
Let $ G = \{ g_1, g_2, \dots, g_k \} \subset \{1, \dots, s-1\} $: set of gas station positions.
Define $ P = \{0\} \cup G \cup \{s\} $, sorted: $ p_0 = 0 < p_1 < \dots < p_{k+1} = s $.
Let $ d_j = p_j - p_{j-1} $ for $ j \in \{1, \dots, k+1\} $: distances between consecutive checkpoints (including start and cinema).
**Constraints**
1. $ 1 \le n \le 2 \cdot 10^5 $, $ 1 \le k \le 2 \cdot 10^5 $, $ 2 \le s \le 10^9 $, $ 1 \le t \le 2 \cdot 10^9 $
2. $ 1 \le c_i, v_i \le 10^9 $ for all $ i $
3. All $ g_i $ are distinct and $ 1 \le g_i \le s-1 $
**Objective**
For a car with tank capacity $ v $, define the minimum time $ T(v) $ to travel distance $ s $ under constraints:
- Normal mode: 1 km in 2 min, consumes 1 L
- Accelerated mode: 1 km in 1 min, consumes 2 L
- Fuel cannot exceed $ v $ at any point
- Fuel can be refilled to full instantly at any $ p_j \in P $
For each segment $ d_j $, the minimal time to traverse it with fuel limit $ v $ is:
$$
T_j(v) =
\begin{cases}
2 d_j & \text{if } d_j \le v \text{ and we use only normal mode} \\
\min_{x \in [0, d_j]} \left( x \cdot 1 + (d_j - x) \cdot 2 \right) \text{ s.t. } 2x + 1(d_j - x) \le v \\
\text{or equivalently: } T_j(v) = d_j + \min(d_j, \max(0, d_j - v))
\end{cases}
$$
Actually, to minimize time: use accelerated mode as much as possible.
Let $ x $ = km driven in accelerated mode, $ d_j - x $ in normal.
Fuel used: $ 2x + 1(d_j - x) = x + d_j \le v \Rightarrow x \le v - d_j $
But $ x \le d_j $, so $ x = \min(d_j, \max(0, v - d_j)) $ is **incorrect**.
Correct:
Fuel constraint: $ 2x + (d_j - x) \le v \Rightarrow x + d_j \le v \Rightarrow x \le v - d_j $
But $ x \ge 0 $, and $ x \le d_j $. So maximum accelerated km: $ x^* = \min(d_j, \max(0, v - d_j)) $?
Wait: $ x \le v - d_j $, so if $ v - d_j \ge d_j \Rightarrow v \ge 2d_j $, then $ x = d_j $, time = $ d_j $
If $ v - d_j < d_j \Rightarrow v < 2d_j $, then $ x = v - d_j $, time = $ x \cdot 1 + (d_j - x) \cdot 2 = d_j + (d_j - x) = d_j + (d_j - (v - d_j)) = 3d_j - v $
So:
$$
T_j(v) =
\begin{cases}
d_j & \text{if } v \ge 2d_j \\
3d_j - v & \text{if } d_j \le v < 2d_j \\
\infty & \text{if } v < d_j
\end{cases}
$$
Then total time: $ T(v) = \sum_{j=1}^{k+1} T_j(v) $
**Objective (final):**
Find $ \min \{ c_i \mid T(v_i) \le t \} $, or $ -1 $ if no such $ i $ exists.
API Response (JSON)
{
"problem": {
"name": "A. Road to Cinema",
"description": {
"content": "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 cine",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF737A"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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 cine...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Vasya 目前位于一家汽车租赁服务点，他希望到达电影院。他购买票的电影将在 #cf_span[t] 分钟后开始。从服务点到电影院有一条长度为 #cf_span[s] 的笔直道路。我们建立一个坐标系，使得汽车租赁服务点位于点 #cf_span[0]，电影院位于点 #cf_span[s]。\n\n道路上有 #cf_span[k] 个加油站，每个加油站都可以免费为汽车加注任意数量的燃油！假设该操作不花费任...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, k, s, t \\in \\mathbb{Z}^+ $: number of cars, number of gas stations, road length, and deadline in minutes. \nLet $ C = \\{ (c_i, v_i) \\mid i \\in \\{1, \\dots, n\\} \\} $: set of c...",
"is_translate": false,
"language": "Formal"
}
]
}