// E. Overtaking
#include<bits/stdc++.h>
using namespace std;
template<typename T>
using vv_t = vector<vector<T>>;
vv_t<pair<long long, int>> arT;
vv_t<long long> neArT;
vector<long long> s;
vector<long long> w;
long long x;
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S) {
// init arT amd meArT
arT = vv_t<pair<long long, int>>(M - 1, vector<pair<long long, int>>(N));
neArT = vv_t<long long>(M - 1, vector<long long>(N));
x = X;
s = vector<long long>(S.begin(), S.end());
w = vector<long long>(W.begin(), W.end());
vector<int> o(N);
std::iota(o.begin(), o.end(), 0);
std::sort(o.begin(), o.end(), [&](int l, int r) { return tie(T[l], w[l]) < tie(T[r], w[r]); });
for (int i = 0; i < N; ++i) {
arT[0][i] = {T[o[i]], o[i]};
neArT[0][i] = T[o[i]] + w[o[i]] * (s[1] - s[0]);
if (i > 0) neArT[0][i] = max(neArT[0][i], neArT[0][i - 1]);
}
// for each M
for (int i = 1; i < M - 1; ++i) {
// sort bus acording to departure first, speed second
std::sort(o.begin(), o.end(),
[&](int l, int r) {
return tie(neArT[i - 1][l], w[arT[i - 1][l].second]) <
tie(neArT[i - 1][r], w[arT[i - 1][r].second]);
});
// go through sorted and compute next arrival time, keep max of others
for (int j = 0; j < N; ++j) {
arT[i][j] = {neArT[i - 1][o[j]], arT[i - 1][o[j]].second};
// make a prefix max array of the next arrival time
neArT[i][j] = arT[i][j].first + w[arT[i][j].second] * (s[i + 1] - s[i]);
if (j > 0) neArT[i][j] = max(neArT[i][j], neArT[i][j - 1]);
}
}
}
long long arrival_time(long long Y) {
// for all M
for (int i = 0; i < arT.size(); ++i) {
// binary search the actual time
int c = upper_bound(arT[i].begin(), arT[i].end(), Y, [&](long long l, pair<long long, int> r) {
return tie(l, x) < tie(r.first, w[r.second]);
}) - arT[i].begin();
// compute next
Y += x * (s[i + 1] - s[i]);
if (c > 0) {
Y = max(neArT[i][c - 1], Y);
}
}
return Y;
}
