#include <bits/stdc++.h>
using namespace std;
namespace {
using i64 = long long;
int N, M, X;
vector<vector<i64>> t, t_s, pref_t;
vector<int> W, S;
} // namespace
void init(int L, int N, vector<i64> T, vector<int> W, int X, int M, vector<int> S) {
::N = N, ::M = M, ::X = X, ::W = W, ::S = S;
{
vector<int> ord(N);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int i, int j) { return W[i] < W[j]; });
vector<i64> _T;
vector<int> _W;
for (int &i : ord) {
if (W[i] > X) {
_T.push_back(T[i]), _W.push_back(W[i]);
}
}
T = _T, ::W = W = _W;
::N = N = W.size();
}
t = vector(M, vector<i64>(N));
t[0] = T;
for (int _ = 1; _ < M; ++_) {
for (int i = 0; i < N; ++i) {
t[_][i] = t[_ - 1][i] + i64(S[_] - S[_ - 1]) * W[i];
}
vector<int> ord(N);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int i, int j) { return t[_ - 1][i] < t[_ - 1][j]; });
for (i64 i = 0, j = 0, p = 0; i < N; ++i) {
t[_][ord[i]] = max(t[_][ord[i]], p);
if (i != N - 1 && t[_ - 1][ord[i]] < t[_ - 1][ord[i + 1]]) {
for (; j <= i; ++j) {
p = max(p, t[_][ord[j]]);
}
}
}
}
t_s = vector(M, vector<i64>(N));
pref_t = vector(M, vector<i64>(N));
for (int i = 0; i < M - 1; ++i) {
vector<int> ord(N);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int ii, int jj) { return t[i][ii] < t[i][jj]; });
t_s[i] = t[i];
sort(t_s[i].begin(), t_s[i].end());
for (int j = 0; j < N; ++j) {
pref_t[i + 1][j] = t[i + 1][ord[j]];
if (j != 0) {
pref_t[i + 1][j] = max(pref_t[i + 1][j], pref_t[i + 1][j - 1]);
}
}
}
}
i64 arrival_time(i64 Y) {
for (int i = 1; i < M; ++i) {
i64 Yn = Y + i64(S[i] - S[i - 1]) * X;
int it = lower_bound(t_s[i - 1].begin(), t_s[i - 1].end(), Y) - t_s[i - 1].begin();
if (it != 0) {
Yn = max(Yn, pref_t[i][it - 1]);
}
Y = Yn;
}
return Y;
}
