#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int MT,XT;
vector<int>ST(1005);
set<pair<ll,ll>>st[1005];
void init(int L,int N,vector<ll> T,vector<int> W,int X,int M,vector<int> S){
for(int i=0;i<M;i++)ST[i]=S[i];
MT=M,XT=X;
vector<pair<ll,int>>tw(N);
for(int i=0;i<N;i++)tw[i]={T[i],W[i]};
sort(tw.begin(),tw.end());
for(int i=1;i<M;i++){
ll t=-1,mp=0,la=0,lan=0;
vector<pair<ll,int>>ntw(N);
for(int j=0;j<N;j++){
if(t==-1)t=tw[j].first;
if(t<tw[j].first){
la=max(la,lan);
st[i-1].insert({t,la});
t=tw[j].first;
}
ntw[j]={max(tw[j].first+tw[j].second*(S[i]-S[i-1]),mp),tw[j].second};
mp=max(mp,ntw[j].first);
lan=max(lan,ntw[j].first);
}
la=max(la,lan);
st[i-1].insert({t,la});
swap(tw,ntw);
sort(tw.begin(),tw.end());
}
return;
}
long long arrival_time(long long Y){
for(int i=0;i<MT-1;i++){
auto r=st[i].lower_bound({Y,0});
ll d=Y+XT*(ST[i+1]-ST[i]);
if(r==st[i].begin())Y=d;
else{
r--;
Y=max(d,(*r).second);
}
}
return Y;
}
