#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
long long off = 0;
vector<pair<long long, long long>> queries;
void init(int L, int N, vector<long long> T, vector<int> W, int X, int M, vector<int> S) {
vector<pair<long long, int>> cur_T;
for (int i = 0; i < N; i++) {
if (W[i] > X) {
cur_T.emplace_back(T[i], W[i]);
}
}
for (int i = 0; i < M - 1; i++) {
sort(cur_T.begin(), cur_T.end());
vector<pair<long long, int>> nxt_T(cur_T.size());
int start = 0;
long long mx = 0;
int dist = S[i + 1] - S[i];
for (int j = 0; j < (int)cur_T.size(); j++) {
if (j > 0 && cur_T[j].first != cur_T[j - 1].first) {
for (int k = start; k < j; k++) {
mx = max(mx, nxt_T[k].first);
}
start = j;
}
nxt_T[j] = {max(mx, cur_T[j].first + 1LL * cur_T[j].second * dist), cur_T[j].second};
}
for (int j = (int)cur_T.size() - 1; j >= 0; j--) {
queries.emplace_back(cur_T[j].first - off, nxt_T[j].first - off - 1LL * X * dist);
}
off += 1LL * X * dist;
cur_T.swap(nxt_T);
}
for (auto [A, B]: queries) {
assert(A >= 0 && B >= A);
}
}
long long arrival_time(long long Y) {
long long res = Y;
for (auto [A, B]: queries) {
if (res > A) {
res = max(res, B);
}
}
res += off;
return res;
}
