Vasya is currently at a car rental service, and he wants to reach cinema. The film he…
- User
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 ci and vi — 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 vi. 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 ci and vi (1 ≤ ci, vi ≤ 109) — the price of the i-th car and its fuel tank capacity.
The next line contains k distinct integers g1, g2, ..., gk (1 ≤ gi ≤ 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.
Examples
Input
3 1 8 10 10 8 5 7 11 9 3
Output
10
Input
2 2 10 18 10 4 20 6 5 3
Output
20
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.
Assistant
We need to parse the problem: There is a road from 0 to s. At point 0 we start with a car that has a full tank of capacity v (liters). There are k gas stations at positions g_i between 0 and s. At gas stations, you can instantly refill any amount for free (so effectively you can consider each segment between stations and start/end as a leg). The car can be driven in two modes: normal: 2 min per km, 1 liter per km. Accelerated: 1 min per km, 2 liters per km. So speeds: normal speed = 0.5 km/min? Actually 1 km in 2 min => speed = 0.5 km/min; accelerated: 1 km per min => speed = 1 km/min. Fuel consumption: normal 1 L/km; accelerated 2 L/km.
We have total distance s. The car has tank capacity v. It can refuel at stations. The start is with full tank. We need to check whether we can travel from 0 to s in time ≤ t, given the capacity v and positions of stations. If yes, then car is feasible. Among n cars (each with price ci, capacity vi) we need minimal price such that feasible. If none, output -1.
We need to compute for a given capacity v, what's the minimal time needed? Because we want to check if minimal time ≤ t. The problem reduces to: given v, determine if there is a feasible driving strategy (choice of mode on each segment, with refueling at stations) that completes within time t. Since we can change modes arbitrarily, the minimal time for a given segment length d with a constraint that fuel used over segments between refueling cannot exceed v (since we start full and can refuel at stations, we can consider each gap between refuel points as independent: we must traverse the gap using at most v fuel, because we can fill up fully at the start of the gap (at station or start) and after traversing the gap we reach the next station where we can refuel. Actually careful: At the start (point 0) we have full tank v. Then we go to first gas station at g1 (if any). That's a segment length d1 = g1 - 0. We must be able to traverse that segment without running out of fuel. Since we can refuel at g1, we can consider that we need to cover distance d1 with initial fuel v, and we can end with any amount (since we can refuel to full). So the constraint: there exists a way (mix of modes) to cover d1 using at most v fuel. Then at g1, we can refuel fully, so we start the next segment with v. So effectively each segment (distance between consecutive fuel stops) must be traversable using at most v fuel. And we can choose modes to minimize total time while respecting fuel consumption constraint (or rather we need to achieve time ≤ t). But the minimal total time overall is the sum over segments of minimal time to cover that segment given we have v fuel capacity? Actually we can choose modes per segment, and fuel usage per segment must not exceed v. For each segment, we need to get from start to end using the car with full tank v, but we can use at most v fuel (since we start with v and cannot exceed v). However, we might use less than v, but that's okay because after the segment we refill to v anyway. So for each segment of length d, we need to determine the minimal possible travel time, given that the total fuel used over the segment ≤ v. But note: we might be able to use less than v, but we want to minimize time, so we will push to use as much accelerated mode as possible, because it's faster but consumes more fuel. However, if we use too much accelerated, we might exceed v. So the optimal strategy for a segment: we need to cover distance d, we have fuel budget v (since we can't exceed that). The question: what's the minimal time to travel d given a fuel limit (max fuel consumption) of v? Since we can mix modes: let x be distance traveled in accelerated mode, and y in normal mode, with x+y = d. Fuel consumption: 2x + 1y = x + d (since y = d - x, so fuel = 2x + (d - x) = d + x). So total fuel = d + x. Time: 1x + 2y = x + 2(d - x) = 2d - x. So time = 2d - x. Thus, increasing x reduces time but increases fuel. So for a given d and fuel capacity v, we need d + x ≤ v => x ≤ v - d. Also x must be between 0 and d. So the maximum allowed x is min(d, v - d)?? Actually x ≤ v - d, provided v - d ≥ 0. Also x cannot exceed d. So the maximal feasible x = min(d, max(0, v - d)). But note: If v < d, then d + x ≤ v would require x ≤ v - d, which is negative if v < d, so no nonnegative x can satisfy if v < d? Let's check: if v < d, then even with x=0, fuel consumption = d > v, so impossible. So the necessary condition: v ≥ d. Actually if v < d, then we cannot cover a segment of length d because even in normal mode (minimum fuel consumption = d) we exceed v. So we need v ≥ d for each segment. That is obvious: we need at least d liters to go distance d because minimum fuel per km is 1.
Thus, for each segment, the minimal possible time given v is when we use as much accelerated mode as possible, i.e., x = min(d, v - d) = max possible x given constraints. Since x can't exceed d, and the constraint from fuel is x ≤ v - d (since d + x ≤ v). So x_max = min(d, v - d). But if v - d >= d, i.e., v >= 2d, then x_max = d, meaning we can go all accelerated, time = 2d - d = d minutes, fuel = d + d = 2d ≤ v if v ≥ 2d, ok. If v is between d and 2d, then v - d < d, so x_max = v - d. Then time = 2d - (v - d) = 3d - v. And fuel = d + (v - d) = v, exactly uses full tank. If v = d, then x_max = 0, time = 2d.
Thus, for a segment length d, the minimal time T(d, v) is:
- If v < d: impossible.
- If d ≤ v ≤ 2d: T = 2d - (v - d) = 3d - v? Wait earlier formula: time = 2d - x, x = v - d => time = 2d - (v - d) = 3d - v. Check: at v = d => T = 3d - d = 2d, correct; at v = 2d => T = 3d - 2d = d, correct.
- If v ≥ 2d: T = d (since x = d).
Also note that T cannot be less than d (since even accelerated gives time = d). So minimal time = max(d, something)? But formula gives d when v>=2d. And for v between d and 2d, T = 3d - v, which decreases linearly from 2d to d. So that matches.
Thus total minimal time overall = sum of T(d_i, v) for all segments (including from last gas station to s? Actually we have start at 0, then stations at g1,...,gk (sorted), and destination at s. So segments: d1 = g1 - 0, d2 = g2 - g1, ..., d_{k+1} = s - gk. We need v ≥ each d_i for feasibility, and total time = Σ T(d_i, v). If total time ≤ t, then car feasible.
So problem: given list of segment lengths d_i (positive) from sorted gas station positions, we need to check for a given v: if v >= max(d_i) (since all d_i <=? Actually need v >= max(d_i) for all segments? Indeed each segment must satisfy v >= d_i, else impossible. So necessary condition: v >= max(d_i). Actually we need v >= max(d_i) because otherwise some segment would be impossible. But is it enough? Yes if v >= each d_i, then each segment is feasible individually. Then we compute total time as sum over segments of T(d_i, v). Note that T(d_i, v) is as defined.
We need to find minimal price among cars with capacity vi such that vi >= max_d and total_time(vi) <= t.
We have up to 2e5 cars, 2e5 gas stations. So we need to process efficiently.
We can compute the segment lengths array after sorting gas station positions. Let m = k+1 segments. Compute d[0..m-1]. Let max_d = max(d_i). For each car, if vi < max_d -> impossible.
Now we need to compute total_time as function of v. Observe that T(d_i, v) is piecewise linear decreasing in v until 2d_i, then constant at d_i.
Thus total_time(v) = Σ f_i(v) where f_i(v) =
- if v < d_i: impossible,
- if d_i <= v <= 2d_i: 3d_i - v,
- if v >= 2d_i: d_i.
So for v >= max_d, total_time(v) = Σ (v <= 2d_i ? 3d_i - v : d_i). Since v will be varying across cars (vi values). We need to compute total_time for many vi efficiently. One approach: sort cars by vi, and compute total_time as a function that is decreasing and piecewise linear. We could precompute the sum over d_i and sum over d_i for which 2d_i <= v, etc. Specifically:
Let total_time(v) = Σ d_i + Σ over segments where v < 2d_i of (2d_i - v?) Wait derive:
For each segment: If v >= 2d_i: T_i = d_i. Else: T_i = 3d_i - v.
So we can write: T_i = d_i + (if v < 2d_i) (2d_i - v)?? Let's see: For v < 2d_i: T_i = 3d_i - v = d_i + (2d_i - v). For v >= 2d_i: T_i = d_i. So indeed T_i = d_i + max(0, 2d_i - v). But careful: This holds for v >= d_i? Actually the expression d_i + max(0, 2d_i - v) yields: if v < 2d_i, then = d_i + 2d_i - v = 3d_i - v. If v >= 2d_i, then = d_i. But note that when v < d_i, the max(0,2d_i - v) still gives 2d_i - v, but then T_i would be d_i + 2d_i - v = 3d_i - v, which is not correct because for v < d_i it's impossible (time would be >2d? Actually 3d_i - v would be >2d_i, but physically impossible because you'd run out of fuel; the condition is v must be >= d_i to be feasible. So we must enforce v >= d_i for feasibility, which we already check. So for v >= max_d (which is >= each d_i), the expression T_i = d_i + max(0, 2d_i - v) holds. Good.
Thus total_time(v) = Σ d_i + Σ max(0, 2d_i - v) = total_distance? Actually Σ d_i = s (total road length). So total_time(v) = s + Σ max(0, 2d_i - v).
So the minimal time given v is s + sum over segments of max(0, 2d_i - v). This is decreasing in v; as v increases, the sum decreases. For v >= 2*max(d_i), sum becomes 0, so total_time = s. So the theoretical minimum time is s (if v is huge, you can go all accelerated, covering each km in 1 minute, total s minutes). Indeed the fastest possible time is s minutes if you have enough fuel capacity to do all accelerated (since each km in accelerated takes 1 min, but uses 2L; if you have enough fuel capacity to cover the longest distance between refueling? Actually we need to consider fuel capacity constraint: Even with huge v, if the segment length d_i is huge? But if v >= 2 * max(d_i), then each segment can be traversed fully in accelerated mode because you need fuel d_i + x where x = d_i (all accelerated) gives 2d_i ≤ v, so yes. So total_time = Σ d_i = s? Wait each segment if all accelerated, time = d_i, sum = s. So indeed minimal time is s. So s ≤ t must hold? If t < s, then impossible regardless of car? But t can be as low as 1 while s>=2, so if t < s, it's impossible because even with infinite fuel capacity, the fastest possible time is s (all accelerated). Actually is that true? The fastest speed is 1 km/min, so covering s km takes at least s minutes. So if t < s, answer should be -1. But check constraints: s up to 1e9, t up to 2e9, so possible t < s. So we need to check that s ≤ t initially; otherwise answer -1 regardless of cars. But problem doesn't state that explicitly; we should check. In examples, s=8, t=10 so s ≤ t. In second, s=10, t=18 so s <= t. So we should incorporate: if s > t, output -1. But is there any possibility to have t < s? Possibly yes, then no car can make it. So early exit.
Now, given v, total_time(v) = s + sum_{i: 2d_i > v} (2d_i - v). Let's define an array of 2d_i values (twice segment lengths). For each segment, we have threshold: if v >= 2d_i, contribution 0; else contribution = 2d_i - v. So sum = Σ_{i: 2d_i > v} (2d_i) - (number of segments with 2d_i > v) * v.
Thus total_time(v) = s + S(v) - cnt(v) * v, where S(v) = sum of 2d_i over segments with 2d_i > v, and cnt(v) = number of such segments.
This is a piecewise linear decreasing function, with breakpoints at v = 2d_i. Since there can be up to 2e5 segments (k+1), we can sort the 2d_i values, and compute prefix sums to evaluate S(v) and cnt(v) quickly for any v via binary search.
We have many queries (cars) but each car's vi can be used to compute total_time(vi) and check if ≤ t, provided vi >= max_d. Among those satisfying, take min ci.
We need to process up to 2e5 cars, so for each car we can compute total_time(vi) in O(log m) using binary search on sorted 2d_i array. That's 2e5 * log(2e5) ~ fine. Alternatively, we can sort cars by vi and then sweep over thresholds, but binary search per car is simpler.
But we must also check that vi >= max_d, else skip.
Now, we must also consider that the gas stations are given in arbitrary order, need to sort them.
Edge cases: k can be 0? The problem says "There are k gas stations along the road", and k ≥ 1 per constraints: 1 ≤ k ≤ 2·10^5. So at least 1 gas station. So segments always include at least two segments? Actually if k ≥ 1, then we have at least one station, so segments: from 0 to first station, between stations, and from last station to s. So m = k+1 ≥ 2.
But what about the case where gas stations might be at 0 or s? They say positions g_i are distinct integers from 1 to s-1, so not at 0 or s. So all d_i > 0.
Now, implement steps:
-
Read n, k, s, t.
-
Read n cars: each (ci, vi). Possibly store in list.
-
Read k gas station positions into array g.
-
Sort g.
-
Compute segment lengths d:
- first: g[0] - 0.
- for i=1..k-1: d_i = g[i] - g[i-1].
- last: s - g[k-1]. Store d array of length m = k+1.
-
Compute max_d = max(d).
-
Compute array twice_d = [2 * di for di in d]; sort twice_d ascending (or descending for binary search?). We'll sort ascending for prefix sums to compute sum of those > v. Actually we need S(v) = sum of 2d_i where 2d_i > v. So if we sort twice_d ascending, we can binary search to find first index where twice_d > v (i.e., upper_bound > v), then cnt = m - idx, and sum = total_sum - prefix_sum[idx]. So we need total_sum of all 2d_i. So sort ascending, compute prefix sums.
-
For each car:
- if vi < max_d: skip (impossible).
- else compute total_time: idx = upper_bound(twice_d, vi) // first element > vi. Actually we need those > v, not >=? Because condition is 2d_i > v gives contribution; if 2d_i == v, then 2d_i - v = 0, so contribution 0, we can treat as not counting. So we want strict > v. So idx = index of first element > vi. In Python: bisect_right? Actually we want elements > v, so we can use bisect.bisect_right(twice_d, vi) to get first index where twice_d > vi? Wait bisect_right returns insertion point to the right of any existing entries equal to v, so the elements >=? Actually if we have values equal to v, bisect_right returns index after the last v, so those equal are not included. So indices from idx to end are > v. That's correct. cnt = m - idx. sum_greater = total_twice_sum - prefix_sum[idx] if idx < m else 0. time = s + (sum_greater - cnt * vi).
- Check if time <= t. If yes, candidate price.
- Keep min price among candidates.
-
If min price found, output; else -1.
-
Also check if s > t: answer -1 (since even with optimal car it's impossible). But we might already catch that because time can't be less than s, but if all cars compute time >= s, and if s > t, no car will satisfy. However, it's possible that due to integer rounding? Actually time is integer? distances and times are integers? Positions are integers, distances are integer differences, so d_i integer, s integer, t integer. Times computed from formulas: time = s + sum(2d_i - v) for those with 2d_i > v. This sum is integer because 2d_i and v are integers. So time integer. So if s > t, no car can have time ≤ t because time ≥ s > t. So we can early return -1. This also saves computation. But careful: Is it always that time ≥ s? Yes because sum(max(0,2d_i - v)) ≥ 0, so time ≥ s. So if s > t, impossible.
Thus we can add early exit: if s > t: print -1; return.
Now we need to test with examples.
Example1: n=3,k=1,s=8,t=10 cars: (10,8), (5,7), (11,9) gas: 3. Sorted g: [3] Segments: d1=3, d2=8-3=5 => d=[3,5]; max_d=5 twice_d = [6,10]; sort -> [6,10]; total_sum=16. For car1: vi=8 >=5. Find idx = bisect_right([6,10],8): first >8? 10>8, idx=1? Actually list=[6,10]. bisect_right(8) returns 1 because 8 >6? Let's compute: bisect_right returns insertion point after any 8. Since 6 <8, and 10 >8, insertion point is 1. So idx=1. cnt = 2-1=1 (element 10). sum_greater= total_sum - prefix[1] = 16-6=10? Wait prefix_sum[1]=6? Actually we need prefix sums array of length m+1: prefix[0]=0, prefix[1]=6, prefix[2]=16. With idx=1, sum_greater = total_sum - prefix[1] = 16-6=10. time = s + (sum_greater - cntvi) = 8 + (10 - 18) = 8+2=10. ≤10? Yes. So feasible. Car2: vi=7 >=5. bisect_right([6,10],7) => idx=1 (since 6<7, 10>7). cnt=1, sum_greater=10, time=8+(10-7)=11. >10 not feasible. Car3: vi=9 >=5. bisect_right([6,10],9) => idx=1? Actually 9 >6, <10, so idx=1. cnt=1, sum_greater=10, time=8+(10-9)=9 ≤10 feasible. So min price among car1 (10) and car3 (11) is 10. Output 10. matches.
Example2: n=2,k=2,s=10,t=18 cars: (10,4), (20,6) gas: 5 3? Actually input: "2 2 10 18" then lines: "10 4" and "20 6" then "5 3". So stations at positions 5 and 3? distinct but arbitrary order. Sort: [3,5]. Segments: d1=3-0=3, d2=5-3=2, d3=10-5=5 => d=[3,2,5]; max_d=5. twice_d = [6,4,10] => sorted: [4,6,10]; total_sum=20. Car1: vi=4 < max_d=5? Actually 4<5 => skip. Car2: vi=6 >=5. bisect_right([4,6,10],6) => insertion point after any 6, so idx=2? Let's compute: list [4,6,10]. bisect_right(6) -> index where to insert 6 to keep order: after existing 6, so at index 2 (since indices: 0:4,1:6,2:10). So idx=2. cnt = 3-2=1 (only 10). sum_greater = total_sum - prefix[2]; prefix: [0,4,10,20]? Actually prefix[0]=0, prefix[1]=4, prefix[2]=10, prefix[3]=20. With idx=2, sum_greater = 20 - 10 = 10. time = s + (10 - 1*6) = 10 + 4 = 14. ≤18? Yes, feasible. So min price =20. Output 20. matches.
So algorithm works.
But wait: In example2, car1 vi=4 is less than max_d=5, so impossible. Good.
Now we must consider potential pitfalls: The segment distances could be large up to s (which is up to 1e9). So 2*d_i can be up to 2e9, which fits in 64-bit (since t up to 2e9, but sum can be larger but we use Python int so fine). Cars vi up to 1e9.
Now what about edge case where v is extremely large (>= 2*max(d_i)). Then total_time = s. So as long as s ≤ t, such cars are feasible. So we need to handle.
Now complexity: O((k log k) + n log k). Which is acceptable.
Now we need to implement carefully.
But wait, there is nuance: The gas stations are at positions g_i. But the car initially has a full tank. At the start, we can consider that we have a gas station at 0? Not exactly; we start with full tank, but no station at 0. However, we treat segment from 0 to first station as a segment that must be covered with initial fuel v. The approach above uses the segment definition and condition v ≥ d1. That's correct.
Also, note that we are allowed to refuel at stations for free instantly. So indeed each segment is independent given full tank at start of segment.
Now, is it always optimal to drive as much accelerated as possible on each segment? Since the time for each segment only depends on v and d_i, and we derived T(d_i, v) = minimal time for that segment given v capacity, independent of other segments. Because you can decide per segment the amount of accelerated distance x_i, subject to fuel consumption: fuel used = d_i + x_i ≤ v. Since after each segment we refuel to v, there is no interaction between segments. So indeed total minimal time is sum of minimal times per segment. So the derived formula is correct.
Now, we must verify that T(d_i, v) = s + Σ max(0,2d_i - v) holds. We did.
Now, consider the scenario: v could be larger than some 2d_i, but not all. That's fine.
Now we need to ensure that our calculation of idx uses bisect_right for strict >. But we need to be careful: If 2d_i == v, then max(0, 2d_i - v)=0, so we shouldn't count it in sum. So we want > v. So bisect_right works.
Now we also need to consider if v is huge, idx will be m (since no element > v). Then cnt = 0, sum_greater = 0, time = s.
Now, consider if v is between d_i and 2d_i for some segments. That's fine.
Now, is there any other nuance: The total time could be fractional? Since distances and times are integers, and consumption rates are integer, the times we derived are integer. So we can compare directly.
Now about sorting gas stations: ensure they are distinct but not necessarily sorted. We'll sort.
Now about the case where there is a segment with d_i = 0? Since gas stations are distinct and between 1 and s-1, distances between consecutive stations could be 0? Actually if two stations at same position? They say distinct, so not same. Could the distance be 0 if g1=0? Not allowed (positions from 1 to s-1), so d_i >0 for all. So no zero.
Now check for large input: using Python, we need fast I/O and binary search using bisect module.
Implementation steps:
- import sys, bisect
- read input lines
- parse ints
- store cars as list of tuples (c, v)
- read gas positions
- sort gas positions
- compute d array: prev = 0 for g in gas_sorted: d.append(g - prev) prev = g d.append(s - prev)
- compute max_d = max(d)
- if s > t: print(-1); return (but we may still compute? Actually it's impossible because time >= s > t, so no car. So early exit.)
- compute twice_d = [2*di for di in d]
- sort twice_d
- compute prefix sums: e.g., prefix = [0]; for val in twice_d: prefix.append(prefix[-1] + val)
- total_twice_sum = prefix[-1]
- best_price = INF (e.g., 10**18)
- iterate over cars: if v < max_d: continue idx = bisect.bisect_right(twice_d, v) cnt = len(twice_d) - idx sum_greater = total_twice_sum - prefix[idx] time = s + (sum_greater - cnt * v) if time <= t: best_price = min(best_price, c)
- if best_price == INF: print(-1) else print(best_price)
Now we must think about overflow? Python int unlimited.
Now test with some custom cases.
Case: s=10, t=10, gas station at 5? Actually k must be >=1, so let's set k=1, station at 5. Then d=[5,5], max_d=5, twice_d=[10,10]. If v=5: time = s + sum(max(0,10-5) each? Actually for each segment, 2d=10 > v=5, so contribution=10-5=5 each, sum=10, time=10+10=20. But using formula: v=5 >= d=5. For each segment, T = 3d - v = 15-5=10? Wait d=5, v=5: T=35-5=10, so total time =20. So time=20 > t=10, not feasible. If v=10: then 2d=10 not > v? Actually condition > v: 10 > 10 false, so contributions=0, time=s=10. So feasible. Indeed v=10 means can go all accelerated? For d=5, v=10 >=25=10, so x_max = d=5, time per segment=5, total=10. So feasible. If v=9: 2d=10>9, contribution=10-9=1 each => total sum=2, time=10+2=12 >10, not feasible. So ok.
Now, what about v=6? contributions=4 each => total=8, time=18 >10.
Now check early exit s>t: e.g., s=10,t=9 => impossible.
Now, confirm that our condition vi >= max_d is necessary but also sufficient? If vi >= max_d, all segments are traversable individually (since v >= d_i). Then the total_time formula holds. So yes.
Now, we should also verify that the sum of T_i we computed is indeed minimal overall time. Could there be a strategy that uses different amounts of fuel on different segments, maybe not always using full tank on some segments? For example, if we use less than full tank on a segment, we might save fuel for later? But we can refuel at stations for free, so there is no need to save fuel. Starting each segment with full tank is always optimal because you can always fill up to v at a station, and you never want less fuel because having more fuel gives you more options (can always waste? but you cannot waste fuel except by using it, but you can drive slower to reduce consumption if needed). Actually having more fuel at the start of a segment never hurts because you can always decide to use less fuel. But the tank capacity is v, so you can always fill to v at a station. So starting each segment with v is optimal. So we can treat segments independently.
Thus the solution is correct.
Now consider if there are multiple cars with same vi but different ci, we choose min ci.
Edge Cases:
-
If k is large (2e5) and m = k+1. Sorting and prefix sums fine.
-
Some cars may have same vi.
-
Some vi may be > 2*max(d_i). Then time = s. If s <= t, they are feasible.
-
If s <= t but we need to ensure vi >= max_d.
Now, test with large values: s=1e9, d_i up to 1e9, twice_d up to 2e9. sum of twice_d could be up to (k+1)21e9, which could be ~4e14? Actually k up to 2e5, so total sum up to 2e5 * 2e9 = 4e14, which fits in Python int.
Now we need to ensure that time computation does not overflow: s up to 1e9, sum_greater up to ~4e14, cnt up to 2e5, v up to 1e9, so sum_greater - cntv could be up to 4e14 - 2e51e9 = 4e14 - 2e14 = 2e14, plus s = 1e9, still fine.
Now, check potential mistake: In the expression time = s + (sum_greater - cnt * v). But recall total_time = s + Σ_{i:2d_i > v} (2d_i - v) = s + Σ_{i:2d_i > v} 2d_i - cnt * v. That's exactly s + sum_greater - cnt * v. So correct.
Now, we also need to consider that the time might be negative? sum_greater - cntv could be negative? But sum_greater is sum of 2d_i for those > v, each of which > v, so sum_greater > cnt * v? Actually if each > v, then sum > cnt * v. So sum_greater - cntv is positive. So time > s.
Now, verify that vi < max_d leads to impossibility. But what if vi is exactly max_d? Then all d_i <= vi, so feasible. However, if vi = max_d and some segment length = max_d, then for that segment v = d, then T = 2d (since v = d). That's fine.
Now, double-check the derivation: For a segment length d and tank v, we assumed that we can traverse the segment with fuel consumption at most v, and we wanted to minimize time. We set x = distance accelerated, y = distance normal, x+y = d, fuel = d + x <= v => x <= v - d. Since v>=d, v-d >=0. Max x = min(d, v-d). So minimal time = 2d - x_max. If v-d >= d, i.e., v>=2d, then x_max = d, time = d. Else x_max = v-d, time = 2d - (v-d) = 3d - v. So yes.
Now check edge: if v is just slightly above d, say v = d + epsilon (like v = d+1 for integer d). Then time = 3d - (d+1) = 2d -1. But wait: time must be at least d (accelerated all). For d=5, v=6, then time = 3*5-6=9. But 9 is between 5 and 10. Let's manually: d=5, v=6. We need to cover 5 km. Normal mode: fuel consumption 5, time 10. Accelerated consumes 2L/km. If we go x km accelerated, y km normal, fuel = 5 + x <=6 => x <=1. So max x=1, time = x + 2y = x+2(5-x)=10 - x, so time =9. Yes. So correct.
Now check if there is any possibility to do better by not refueling to full at some stations? That would only reduce available fuel for later segments, potentially requiring to use less accelerated mode earlier, which could increase time. So not beneficial.
Thus algorithm correct.
Now we can code.
But wait: The problem states: "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." So it's free and instant. So indeed always fill to full at each station if possible (unless you don't need to?). But if you have enough fuel left to cover next segment without filling, filling to full doesn't hurt; you can still drive as you like. But maybe you might not want to fill if you want to waste time? No, we want minimize time.
So always fill to full because having more fuel allows more accelerated driving which reduces time.
Thus solution stands.
Now we should also consider that we might not need to stop at a gas station if we have enough fuel to go through multiple segments? But you can only refuel at stations; you might skip refueling if you have enough fuel to cover multiple segments. But is that potentially beneficial? Let's analyze: If we have a large tank capacity v, we could potentially go through several consecutive segments without refueling, which might affect the optimal time? Because if we skip refueling, we don't get the benefit of resetting the tank to full, but we might be able to use the fuel saved from not refueling? Actually refueling is free and instant, so there's no cost to refuel. If you skip refueling when you have enough fuel to cover more than one segment, you are essentially imposing a constraint that the total fuel consumption over multiple segments must not exceed v (since you start with v at the start of the first segment and then you don't refuel). But if you refuel, you reset to v for each segment, thus each segment individually must satisfy fuel ≤ v. If you skip refueling, you impose a combined constraint: sum of (d_i + x_i) over those segments ≤ v. But since you can refuel for free, why would you skip? Because if the combined constraint is less restrictive than individual constraints? Actually individual constraints require each segment's fuel ≤ v. Combined constraint could be more restrictive because you have to sum. But could it be less restrictive? Possibly if one segment's required fuel for minimal time is less than v, you could use the leftover fuel on the next segment to allow more accelerated there? But wait, if you refuel at the station, you also get full tank, so you could still use the leftover fuel? Actually if you refuel, you fill up to v, which is at least as much as whatever leftover you had. So refueling gives you v fuel at the start of next segment. If you skip, you start with whatever fuel left from previous segment, which is ≤ v. So skipping gives you at most the same amount of fuel, often less. So refueling gives you more fuel, which can't hurt for minimizing time because more fuel allows more accelerated mode (faster). So skipping refueling cannot lead to lower total time than refueling at each station. Because you can always decide not to use all fuel even if you refuel; but if you skip, you might be forced to use less fuel on the earlier segment to save for later, which could reduce the amount of accelerated you can use, increasing time. So optimal strategy will refuel at every station to maximize fuel availability for each segment. So we can assume we always refuel.
Thus our segment independence assumption holds.
Now, check if any corner case: Suppose there is a segment length d such that v is just enough to allow x_max = v - d, but if v - d is less than d, then T = 3d - v. That's the minimal time for that segment given we start with v fuel. If we combine two segments, we might be able to allocate more accelerated on one segment and less on the other, achieving a lower total time than the sum of the independent minimal times? Let's think: Suppose two segments lengths d1 and d2, v is such that for each individually, we can't do full accelerated on both because fuel per segment would be 2d_i > v? Actually if v is less than 2d_i for each, individually you'd have to limit accelerated. But if you combine them, the total fuel needed for both segments is (d1 + x1) + (d2 + x2) ≤ v (since no refuel). The total time = 2(d1+d2) - (x1 + x2). To minimize time, we want to maximize x1+x2 subject to x1 ≤ d1, x2 ≤ d2, and (d1 + x1) + (d2 + x2) = (d1+d2) + (x1+x2) ≤ v. So maximize X = x1+x2 subject to 0 ≤ x1 ≤ d1, 0 ≤ x2 ≤ d2, and X ≤ v - (d1+d2). So the total maximum X is min(d1+d2, v - (d1+d2)). So if v ≥ 2(d1+d2), we can set X = d1+d2, i.e., all accelerated, total time = d1+d2. If (d1+d2) ≤ v ≤ 2(d1+d2), then X = v - (d1+d2), total time = 2(d1+d2) - (v - (d1+d2)) = 3(d1+d2) - v. That's exactly the same formula as for a single segment of length d1+d2 with tank v. Meanwhile, if we refuel at the station, we get times: For segment1, max x1 = min(d1, v - d1); for segment2, max x2 = min(d2, v - d2). The total accelerated distance is x1 + x2, and total time = (2d1 - x1) + (2d2 - x2) = 2(d1+d2) - (x1+x2). So the question is: is x1+x2 under individual constraints at most the combined max X? Since individually x1 ≤ v - d1, x2 ≤ v - d2, so x1+x2 ≤ 2v - (d1+d2). But the combined constraint is x1+x2 ≤ v - (d1+d2). For v between d1+d2 and 2(d1+d2), which is more restrictive? 2v - (d1+d2) vs v - (d1+d2). Since v is positive, 2v - (d1+d2) > v - (d1+d2). So the individual constraints could allow a larger sum than the combined constraint? Let's test: Suppose v=12, d1=5, d2=5. Individual: v - d1 = 7, but x1 ≤ d1=5, so x1 max =5; similarly x2 max=5; so individually max x1+x2 =10. Combined: total length 10, v=12, v - (d1+d2) =2, so X ≤ 2? Wait v=12, d1+d2=10 => v-(d1+d2)=2, but also X ≤ d1+d2=10, so X ≤2. That's much smaller. So individual refueling yields much higher accelerated total (10) compared to combined (2). But why is that? Because in combined case, the fuel consumption for segment1 and segment2 together must not exceed v=12. But if we go all accelerated on both segments individually, fuel consumption would be 25=10 per segment? Actually, for segment1: fuel consumption if all accelerated = 2*5=10, which already exceeds v=12? Wait careful: For a segment of length d, fuel consumption if all accelerated = 2d. So for d=5, 2d=10. So if we go all accelerated on segment1, we need 10 fuel, leaving only 2 fuel for segment2, which would allow at most 2 km in accelerated? Actually you'd need to cover segment2, minimum fuel even if all normal = d2 =5, but we only have 2 left, impossible. So actually for combined, you cannot do all accelerated on both because total fuel needed would be 10+10=20 >12. So the combined constraint is more restrictive. So refueling at the station allows you to "reset" the fuel tank, giving you v fuel for each segment. So indeed refueling is better.
Thus our assumption that refueling at each station gives the minimal total time is correct. So no need to consider skipping stations.
Thus solution is correct.
Now we must consider memory: arrays of size up to 2e5, fine.
Now, time complexity: sorting gas stations O(k log k), sorting twice_d (we need sorted, but we already have d array, we compute twice_d and sort it; that's O(m log m). Since m = k+1 <= 200001, fine.
Now, what about input: The first line contains four positive integers n, k, s, t. So we need to parse them.
Edge Cases:
-
If there are multiple gas stations, but some segments could be very long. Our formula handles.
-
Ensure that we treat positions as integers and compute distances correctly.
Now, test with a scenario where t is exactly s, and v huge: Then time = s, so car feasible if v >= max_d. So we need to pick cheapest car with v >= max_d and v large enough to make time = s? Actually if v >= 2 * max_d, time = s. But if v is between max_d and 2max_d, time = s + sum(max(0,2d_i - v)) > s. So if t = s, only cars with v >= 2 * max_d (or possibly some combination such that sum of excess is 0) are feasible. But sum of excess is zero only if for all i, 2d_i <= v. That is v >= 2 * max(d_i). Actually need v >= max(2d_i) = 2 * max(d_i) (since d_i positive). So condition for time = s is v >= 2max_d. So if t = s, we need v >= 2*max_d. But also v >= max_d (implied). So we need to check condition accordingly. Our binary search formula will compute time correctly.
Now, the problem statement says "not later than in t minutes". So time <= t inclusive.
Now, check for possible overflow or negative time: sum_greater - cnt*v could be negative if v > some 2d_i? But it's only for those with 2d_i > v; for those, 2d_i - v > 0, sum_greater is sum of 2d_i for those > v, and each such 2d_i > v, so sum_greater > cnt * v (since each term > v). So positive. So time > s.
Now, some implementation details:
- Use sys.stdin.read() to read all ints quickly.
- Or sys.stdin.buffer.
Simplify: We'll read line by line.
Let's implement:
def solve(): import sys, bisect data = sys.stdin.read().split() it = iter(data) n = int(next(it)) k = int(next(it)) s = int(next(it)) t = int(next(it)) cars = [] for _ in range(n): c = int(next(it)); v = int(next(it)) cars.append((c, v)) stations = [int(next(it)) for _ in range(k)] stations.sort() # compute segments d = [] prev = 0 for g in stations: d.append(g - prev) prev = g d.append(s - prev) # last segment max_d = max(d) # early check: if s > t: impossible if s > t: print(-1) return # compute twice_d sorted twice_d = [2 * di for di in d] twice_d.sort() prefix = [0] for val in twice_d: prefix.append(prefix[-1] + val) total_twice = prefix[-1] m = len(twice_d) best = None for c, v in cars: if v < max_d: continue idx = bisect.bisect_right(twice_d, v) # first index where > v cnt = m - idx sum_greater = total_twice - prefix[idx] time = s + (sum_greater - cnt * v) if time <= t: if best is None or c < best: best = c if best is None: print(-1) else: print(best)
Now, test with given examples.
I'll run mental test: already did.
Potential off-by-one: When idx = m (i.e., v >= all twice_d), then cnt = 0, sum_greater = 0, time = s. Works.
Now, consider if there is any segment where 2d_i equals v. Since we use bisect_right, those are excluded because we require > v. So contribution 0. That's correct.
Now, consider if v is exactly max_d, but some 2d_i > v maybe. Works.
Now, think about the case where k=0? Problem says k >= 1. So ignore.
Now, what about if the gas station positions are not sorted? We sort.
Now, ensure that we compute d correctly: after sorting stations, we need to consider segments: from 0 to first station, between stations, and from last station to s. Yes.
Now, think about potential integer overflow in languages but Python fine.
Now, let's think about time limit: O((n+k) log k) should be okay for 2e5.
But we might optimize by sorting cars by v and then scanning, but not necessary.
Now, double-check the formula with another example: Suppose s=100, t=150, two stations at positions 30 and 70. So d=[30,40,30]. max_d = 40. twice_d = [60,80,60] sorted => [60,60,80]. total_twice = 200. For v=60: v>=max_d? max_d=40, yes. idx = bisect_right([60,60,80],60) => index of insertion after all 60s, so idx = 2 (since two 60s, positions 0 and 1, after them idx=2). cnt = 3-2=1 (only 80). sum_greater = 200 - prefix[2] where prefix: [0,60,120,200], prefix[2]=120, sum=80. time = s + (80 - 1*60)=100+20=120 <=150, feasible. Let's manually compute: Segments: d1=30, d2=40, d3=30. v=60. For each segment:
- d1=30: v>=30, v<230=60? v=60, 2d=60, not > v? Actually v=60, 2d=60, condition is 2d>v? Since equality gives 0, so for d1, 2d=60 == v, so contribution 0, T1 = d1=30 (since v>=2d? Actually v=2d, so we can go all accelerated? v=60, 230=60, so yes x_max = d, T=30). So T1=30.
- d2=40: 2d=80>60, so T2 = 3*40 - 60 = 120-60=60? Actually formula: v between d and 2d: T=3d - v = 120-60=60. Or from our expression: time = d_i + (2d_i - v) = 40 + (80-60)=60.
- d3=30: same as d1, T3=30. Total=30+60+30=120. matches.
Now v=50: v>=max_d? max_d=40, yes. idx = bisect_right([60,60,80],50) => first >50 is 60 at index 0, so idx=0, cnt=3, sum_greater=200, time=100+(200-350)=100+200-150=150. Feasible if t=150. Check manually: d1: v=50<60? 2d=60>50, T1=330-50=90-50=40? Actually 330=90, minus 50=40. d2: T2=340-50=120-50=70. d3: same as d1=40. total=40+70+40=150. So matches.
Now v=40: v>=max_d? max_d=40, ok. idx = bisect_right([60,60,80],40) => idx=0, cnt=3, sum_greater=200, time=100+(200-3*40)=100+200-120=180. So >150, not feasible. Indeed v=40 is minimal to traverse all segments, but time high.
So algorithm works.
Now consider case with t < s. Then early exit -1. Let's test: s=5, t=4, any cars? We output -1 regardless of cars. That's correct because even with infinite v, time min = s =5 > t.
Now, one more nuance: What if there is a car with v very large but we also need to consider that the stations exist? Our formula yields time = s for v >= 2max_d. So if s <= t, such car works. So answer could be cheapest car with v >= max_d and also time <= t. But note that time may be > s even if v >= 2max_d? Actually time = s only if v >= 2 * max_d. But if max_d is large, v >= max_d might not be enough to get time = s, but if t > s, maybe a car with v between max_d and 2*max_d might also work if extra time sum is not too large. So we need to check both conditions.
Now, ensure we consider all cars. The naive per-car binary search is fine.
Potential optimization: we can sort cars by v, and then for increasing v, total_time(v) is non-increasing. So we could find minimal v that works, then pick cheapest car with v >= that threshold but also ci minimal? But we have two dimensions: we want min ci, not necessarily min v. So a car with higher v might be cheaper than one with lower v. So we cannot just threshold v. We need to check all. However, we could precompute for each car if feasible and take min ci.
Given constraints 2e5, O(n log n) is fine.
Now we need to ensure we read all inputs correctly.
Edge Cases: If gas stations are not sorted and some positions may be > s? The problem says 1 ≤ gi ≤ s-1, so fine.
Now, about memory: we can store cars list.
Now, think about using Python's bisect from built-in.
Now, check for possible error: We used bisect_right(twice_d, v). But twice_d sorted ascending. For v = exactly 2*d for some d, we exclude that segment from sum. That's correct. However, what if there are multiple same values? Works.
Now, think about if v is less than max_d, we skip. That's necessary because our formula would give negative time? Actually if v < max_d, there is at least one segment where v < d_i, which is impossible. So we must skip.
Now, what about if v is exactly max_d, but some other segment longer? Actually max_d is the maximum, so v >= max_d ensures v >= all d_i. So ok.
Now, confirm that time formula works when v exactly equals d for a segment: Then 2d > v (since 2d > d), so contribution = 2d - d = d, time = s + d? Actually for that segment, T = 2d, which is d + (2d - d) = d + d = 2d. So our formula: time = s + Σ (2d_i - v) for those with 2d_i > v. For that segment, 2d_i - v = d. So total_time = s + ... includes d. But s already includes d_i as part of sum of distances. So total_time = s + sum of (2d_i - v) for those 2d_i > v = Σ d_i + Σ (2d_i - v) = Σ (3d_i - v) for those with 2d_i > v, plus Σ d_i for others. For the segment where v = d, 2d > v so time contributed = 3d - v = 2d, which matches. So formula holds.
Now, we should test for integer overflow in other languages, but Python fine.
Now, we can implement.
But wait: There might be a nuance: The problem states: "It's not allowed to fuel a car with more fuel than its tank capacity vi. All cars are completely fueled at the car rental service." So initial full tank.
Our analysis assumes we can refuel to full capacity at each station. However, there is a subtlety: If we refuel at a station, we can fill any amount, but we are limited by capacity vi. So we can always fill up to vi. So yes.
Now, ensure that we treat the situation when we reach a station with some fuel left: we can add fuel up to vi. That's fine.
Now, confirm that the car must travel from 0 to s, and we can change driving mode at any time. So our segment approach works because we treat each segment independently: at the start of a segment (either at 0 or at a station), we have a full tank (vi). We choose how much accelerated distance to use to traverse the segment, ensuring total fuel used does not exceed vi. Since we can change mode arbitrarily along the segment, the optimal is to do accelerated as much as possible, then normal. Indeed, we could also intermix, but any strategy can be represented by a total accelerated distance x, as fuel consumption and time are linear.
Thus solution is correct.
Now, check if there is any possibility to benefit from not refueling to full at a station? That would only reduce fuel for next segment, potentially causing a need to go slower, which would increase time. So no.
Now, verify with some random test by brute force for small sizes. Not needed but mental.
Now, consider case where k is large and all stations are at same position? But positions are distinct, so not possible.
Now, check for performance: Sorting twice_d of size up to 200001, then for each car binary search O(log m). n up to 200000, so total ~ 200k * log(200k) ~ 200k * 18 = 3.6M, fine.
Now, implement.
But we need to be careful: The input might have cars with price and capacity up to 1e9, so best price could be up to 1e9, but we need to output -1 if none.
Now, potential pitfalls: The sum_greater - cnt * v may be large; but time must be compared to t, which is up to 2e9, but time can be as high as 2s? Actually time maximum occurs when v = max_d (minimum feasible). Then each segment with 2d_i > v contributes (2d_i - v). Worst-case, if v = max_d, and max_d might be close to s? But s could be 1e9. For example, if k=0? Actually k>=1, so segments at least 2. But worst-case, one segment could be nearly s (if stations are near start and end). For instance, stations at s-1 and something? Actually if k=1, stations at 1, then segments: d1=1, d2=s-1. So max_d = s-1, almost s. Then v = s-1 (just feasible). Then for the large segment d2 = s-1, 2d2 = 2(s-1) > v, contribution = 2(s-1) - (s-1) = s-1. For small segment, maybe 21 - (s-1) negative? Actually for d1=1, 2*1=2 <= v? v = s-1, which is huge, so 2 <= v, so no contribution. So total time = s + (s-1) = 2s-1, which could be up to 2e9. t up to 2e9, so fits. But could be larger than t. So our comparisons fine.
Now, ensure we use int.
Now, let's test more.
Edge: If there is a car with v exactly max_d, but max_d is very small relative to s? Not relevant.
Now, we should also consider that the input might have n=0? No, n>=1.
Now, final code.
But before final, consider potential alternative approach: Could there be a scenario where you might not want to fully use accelerated mode even if you have fuel? Because using accelerated mode reduces time, so you always want to use as much as possible given fuel constraint. So yes.
Thus solution stands.
Now, implement in Python.
I'll write a solve() function and call it.
Potential micro-optimizations: Using local variables for bisect, prefix, etc.
Now, test with sample.
Also, test with some custom:
Case: n=1, k=1, s=10, t=9 (impossible due to s>t). Output -1.
Case: n=1, k=1, s=10, t=10, stations at 5, car c=5, v=10 (>=max_d=5, and v=10>=2max_d? 25=10, so time=s=10). Should output 5. Our code: d=[5,5]; max_d=5; v=10>=5; twice_d=[10,10]; idx=bisect_right([10,10],10)=2; cnt=0; time=10; <=t; best=5 -> prints 5.
Case: n=1, k=1, s=10, t=10, stations at 5, car c=5, v=9. v>=5, twice_d sorted=[10,10]; idx=bisect_right(9)=0? Since 9 <10, idx=0, cnt=2, sum_greater=20, time=10+(20-18)=12 >10 -> not feasible. So correct.
Case: n=1, k=1, s=10, t=11, car v=9, time=12 >11 -> not feasible. So v=9 not enough; need v>=10 to achieve time 10? Actually v=9 gives time=12; v=10 gives time=10; v=8? v<max_d=5? Actually v=8>=5, time with v=8: idx= bisect_right(8)=0, cnt=2, sum_greater=20, time=10+(20-16)=14. So yes.
Now, consider case with multiple stations and v threshold.
All good.
Now, final answer: Implement as described.
But wait: There is nuance about the starting point: we said we have a station at 0? No, but we start with full tank. So we treat first segment from 0 to first station. That's correct.
Now, is there any scenario where we could skip a station to combine segments and get lower time than sum of individual minima? Let's examine thoroughly: The minimal time for a given v and segments is not necessarily the sum of per-segment minima if you skip refueling? Because per-segment minima assume you start each segment with a full tank. If you skip refueling, you start the next segment with leftover fuel, which is at most v - (d1 + x1). So you may have less fuel than full, thus the per-segment constraint becomes stricter for that segment, potentially reducing the amount of accelerated you can use on it. But could it be beneficial to not refuel because using less fuel on first segment leaves more for second, maybe allowing more accelerated overall? Actually per-segment minima assume you have v fuel at the start of each segment. If you skip refueling, you have less than v at start of second segment. That cannot increase the total possible accelerated distance across both segments because the total fuel available for both segments is v (initial). With refueling, you have v for first segment and then another v for second, effectively double the fuel budget. So skipping reduces total fuel available for the two segments combined. So it's never beneficial for minimizing time. However, there is a subtle point: The per-segment minima approach uses the fact that after refueling, you can use v fuel for the second segment, which is more than leftover if you didn't refuel. So you can always achieve at least as much accelerated (and thus less time) by refueling. Therefore, sum of per-segment minima is the minimal total time. So correct.
Thus final solution is valid.
Now, we will produce final answer.
But before finalizing, think about potential alternative interpretation: The car's tank capacity is vi liters. When refueling, you can add any amount, but you cannot exceed vi. So you can only have up to vi fuel in the tank at any time. Starting with vi. So after traveling a segment, you might have some fuel left. When you refuel, you can fill up to vi, but you might choose not to fill fully if you want to save fuel? But fuel is free, so filling fully gives you more options; there's no downside. So always fill to full.
Thus we are good.
Now, one more nuance: The problem says "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." This implies that we can change continuously, so our model of x accelerated km and y normal km is accurate.
Now, what about the possibility of using a mixture within a segment to achieve any time between? The formula we derived is optimal because it's linear: time decreases with x, and x is limited by fuel constraint and max x = d. So to minimize time, maximize x. So it's correct.
Now, we are ready to code.
But we need to handle input where there are no gas stations? The constraints say k ≥ 1, so we don't need to handle k=0. However, it's safe to handle k=0? The problem statement says 1 ≤ k, so fine.
Now, final code:
def solve(): import sys, bisect data = sys.stdin.buffer.read().split() if not data: return it = iter(data) n = int(next(it)) k = int(next(it)) s = int(next(it)) t = int(next(it)) cars = [] for _ in range(n): c = int(next(it)) v = int(next(it)) cars.append((c, v)) stations = [int(next(it)) for _ in range(k)] stations.sort() d = [] prev = 0 for g in stations: seg = g - prev d.append(seg) prev = g d.append(s - prev) max_d = max(d) if s > t: print(-1) return twice_d = [di * 2 for di in d] twice_d.sort() prefix = [0] for val in twice_d: prefix.append(prefix[-1] + val) total_twice = prefix[-1] m = len(twice_d) best = None for c, v in cars: if v < max_d: continue idx = bisect.bisect_right(twice_d, v) cnt = m - idx sum_greater = total_twice - prefix[idx] time = s + (sum_greater - cnt * v) if time <= t: if best is None or c < best: best = c print(-1 if best is None else best) if __name__ == "__main__": solve()We need to ensure we use sys.stdin.buffer for fast reading.
Now, test with examples.
Let's simulate with example1 using code:
n=3, k=1, s=8, t=10, cars: (10,8), (5,7), (11,9), stations: [3]. Sorted. d=[3,5]; max_d=5; twice_d=[6,10]; sorted [6,10]; prefix [0,6,16]; total_twice=16; m=2. Car1: v=8>=5; idx=bisect_right([6,10],8)=1; cnt=1; sum_greater=16-6=10; time=8+(10-8)=10; best=10. Car2: v=7; idx=bisect_right([6,10],7)=1; cnt=1; sum_greater=10; time=8+(10-7)=11>10 skip. Car3: v=9; idx=1; cnt=1; sum_greater=10; time=8+(10-9)=9; best=10 (since 11>10, but 9<10? Actually 9<10? Wait best is min price; car3 price 11 >10, so best remains 10). So output 10. Good.
Example2: n=2,k=2,s=10,t=18; cars: (10,4),(20,6); stations: [5,3] -> sorted [3,5]; d: 3-0=3,5-3=2,10-5=5 => d=[3,2,5]; max_d=5; twice_d=[6,4,10] sorted [4,6,10]; prefix [0,4,10,20]; total=20; m=3. Car1: v=4<max_d skip. Car2: v=6; idx=bisect_right([4,6,10],6) -> after all 6? list [4,6,10]; bisect_right for 6 returns index after last 6, which is 2 (since positions: 0:4,1:6, insertion point after 6 is 2). cnt=3-2=1; sum_greater=20-10=10; time=10+(10-6)=14 <=18, best=20. Output 20. Good.
Now test with s > t case: Should print -1. We'll trust.
Now, test with scenario where best price is not the smallest v. Let's create: n=2, k=1, s=100, t=150, stations [50]. d=[50,50]; max_d=50; twice_d=[100,100]; total=200. Car1: c=100, v=60 -> time=100+(200-2*60? Actually idx: bisect_right([100,100],60)=0; cnt=2; sum_greater=200; time=100+200-120=180 >150 =>