#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;
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++) 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;
}
}
long long arrival_time(long long Y)
{
ll ans = Y;
for (int i = 0; i < M - 1; i++) {
ll orig = ans + (ll)(S[i+1] - S[i]) * X;
for (auto [l, r] : cars[i]) if (l < ans) ckmax(orig, r);
ans = orig;
}
return ans;
}
