#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<ll> start; // start time of each bus
vector<int> speed;//bus speed
vector<int> stops;
int len; // size of road
int n, m; // number of buses and stations
int xsp; // reserve travel time
vector<tuple<ll, ll, bool>> currTimes;
vector<vector<pair<ll, ll>>> r;
void init(int L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> S) {
len = L;
n = N;
start = T;
speed = W;
xsp = X;
m = M;
stops = S;
for (int i = 0; i < n; i++) {
currTimes.push_back({start[i], speed[i], false});
}
for (int i = 0; i < m-1; i++) {
r.push_back({});
sort(currTimes.begin(), currTimes.end());
vector<tuple<ll, ll, bool>> nxt;
ll maxTime = -1;
ll dis = stops[i+1] - stops[i];
for (auto [currTime, sp, special]: currTimes) {
ll nxtTime = currTime + sp * dis;
if (currTime < maxTime) nxtTime = max(nxtTime, maxTime);
maxTime = max(maxTime, nxtTime);
nxt.push_back({nxtTime, sp, special});
r.back().push_back({currTime, nxtTime});
}
sort(r.back().begin(), r.back().end());
ll mx = r.back()[0].second;
for (int i = 1; i < r.back().size(); i++) {
mx = max(mx, r.back()[i].second);
r.back()[i].second = mx;
}
currTimes = nxt;
}
}
ll arrival_time(ll st) {
ll ans = st;
for (int i = 0; i < m-1; i++) {
int len = r[i].size();
ll dis = stops[i+1] - stops[i];
ll nxt = ans + dis * xsp;
int lo = 0, hi = len-1;
int idx = -1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (r[i][mid].first < ans) {
idx = mid;
lo = mid+1;
}
else hi = mid-1;
}
if (idx == -1) {
ans = nxt;
continue;
}
nxt = max(nxt, r[i][idx].second);
ans = nxt;
}
return ans;
}
/*
int main() {
init(6, 4, {20, 10, 40, 0}, {5, 20, 20, 30}, 10, 4, {0, 1, 3, 6});
cout << arrival_time(0) << '\n';
cout << arrival_time(50) << "\n";
}*/
