#include <bits/stdc++.h>
#define ll long long
#define ar array
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#include "overtaking.h"
using namespace std;
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
int L, N, X, M;
vector<ll> T;
vector<int> W, S;
vector<vector<ar<ll, 2>>> cars;
vector<ar<ll, 4>> tot;
const ll INF = 4e18;
void init(int _L, int _N, std::vector<long long> _T, std::vector<int> _W, int _X, int _M, std::vector<int> _S)
{
L = _L;
N = _N;
T = _T;
W = _W;
X = _X;
M = _M;
S = _S;
W.push_back(X);
vector<ar<ll, 2>> buses;
for (int i = 0; i < N; i++) if (W[i] > X) buses.push_back({T[i], i});
cars.resize(M);
for (int i = 0; i < M - 1; i++) {
vector<ar<ll, 3>> ints;
for (auto [x, y] : buses) {
ints.push_back({x, x + (ll)W[y] * (S[i+1] - S[i]), y});
}
sort(all(ints));
ll to = 0;
vector<ar<ll, 2>> buses2;
vector<ar<ll, 2>> tmp;
for (auto [l, r, idx] : ints) {
ckmax(to, r);
buses2.push_back({to, idx});
tmp.push_back({l, to});
}
swap(buses, buses2);
cars[i] = tmp;
}
for (int i = 0; i < M-1; i++) {
ll R = -1;
vector<ar<ll, 2>> nw;
sort(all(cars[i]), [&](const auto &A, const auto &B) { return A[0] != B[0] ? A[0] < B[0] : A[1] > B[1]; });
for (auto [l, r] : cars[i]) {
if (r <= R) continue;
R = r;
nw.push_back({l, r});
}
swap(cars[i], nw);
}
vector<ar<ll, 4>> cur;
for (int i = M-2; i >= 0; i--) {
ll cur_dist = (ll)(S[i+1] - S[i]) * X;
assert(is_sorted(all(cars[i])));
vector<ar<ll, 3>> ints;
/*
cout << "Dist " << cur_dist << '\n';
cout << "Cars\n";
for (auto [l, r] : cars[i]) cout << l << " " << r << '\n';
*/
for (int j = 0; j < sz(cars[i]); j++) {
ll nxt = j+1 < sz(cars[i]) ? cars[i][j+1][0] : cars[i][j][1];
ll right = min(cars[i][j][1] - cur_dist, nxt);
if (cars[i][j][0] + 1 <= right) ints.push_back({cars[i][j][0] + 1, right, cars[i][j][1]});
}
for (int i = 1; i < sz(ints); i++) assert(ints[i-1][1] < ints[i][0]);
for (auto [l, r, dest] : ints) assert(r + cur_dist <= dest);
if (i == M-2) {
for (auto [l, r, dest] : ints) cur.push_back({l, r, dest, i+1});
}
else {
assert(is_sorted(all(cur)));
int on = 0;
vector<ar<ll, 4>> here;
for (auto [l, r, dest] : ints) {
while (on < sz(cur) && cur[on][1] < dest) on++;
if (on < sz(cur) && cur[on][0] <= dest) {
here.push_back({l, r, cur[on][2], cur[on][3]});
}
else {
here.push_back({l, r, dest, i+1});
}
}
swap(cur, here);
}
/*
cout << "Ints\n";
for (auto [l, r, dest] : cur) cout << l << " " << r << " " << dest << '\n';
cout.flush();
*/
}
tot = cur;
}
long long arrival_time(long long Y)
{
auto it = upper_bound(all(tot), ar<ll, 4>{Y, -1, -1, -1});
bool cov = it != tot.begin() && (*prev(it))[1] >= Y;
return cov ? (*prev(it))[2] + (ll)(S[M-1] - S[(*prev(it))[3]]) * X : Y + (ll)(S[M-1]-S[0]) * X;
}
