#include <bits/stdc++.h>
#include "overtaking.h"
using namespace std;
using ll = long long;
int L, M;
ll X;
vector<vector<pair<ll, ll>>> v, f;
vector<int> S;
void init(int Lin, int N, vector<ll> T, vector<int> W, int Xin, int Min, vector<int> Sin){
L = Lin, M = Min, X = Xin, S = Sin;
vector<int> ord(N);
for(int i = 0; i < N; i++) ord[i] = i;
sort(ord.begin(), ord.end(), [&](int i, int j){return T[i] < T[j];});
v.resize(M);
for(int i : ord){
if(W[i] <= X) continue;
if(v[0].empty()) v[0].emplace_back(T[i], (ll)W[i]);
else v[0].emplace_back(T[i], (ll)W[i]);
}
sort(v[0].begin(), v[0].end());
f.resize(M-1);
for(int k = 1; k < M; k++){
ll d = S[k]-S[k-1];
ll last = 0;
for(auto [t, w] : v[k-1]){
ll e = t+w*d;
ll t2 = max(last, e);
v[k].emplace_back(t2, w);
f[k-1].emplace_back(t, t2);
last = t2;
}
sort(v[k].begin(), v[k].end());
}
}
ll arrival_time(ll Y){
ll t = Y;
for(int k = 0; k < M-1; k++){
ll d = S[k+1]-S[k];
ll e = t+d*X;
ll bound = 0;
auto it = lower_bound(f[k].begin(), f[k].end(), make_pair(t, 0ll));
if(it != f[k].begin()){
it--;
bound = it->second;
}
t = max(e, bound);
}
return t;
}
