#include "overtaking.h"
#include<bits/stdc++.h>
using namespace std;
#define PB push_back
#define MP make_pair
#define P push
#define I insert
#define F first
#define S second
typedef long long ll;
ll n,m,l,spn;
vector<ll> sp;
vector<ll> t[1000],e[1000];
vector<pair<ll,ll > > v[1000];
vector<ll> vt[1000];
vector<ll> len;
void init(int L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> SP){
n=(ll)N;m=(ll)M;l=(ll)L;spn=(ll)X;
for(int i=0;i<n;i++){
sp.PB((ll)W[i]);
t[0].PB(T[i]);
len.PB((ll)SP[i]);
}
for(int j=1;j<m;j++){
vector<pair<ll,pair<ll,ll> > > temp;
for(int i=0;i<n;i++){
e[j].PB(t[j-1][i]+(len[j]-len[j-1])*sp[i]);
t[j].PB(-1);
temp.PB(MP(t[j-1][i],MP(sp[i],i)));
}
sort(temp.begin(),temp.end());
ll cur=-1;
for(int i=0;i<n;i++){
int y=temp[i].S.S;
cur=max(cur,e[j][y]);
t[j][y]=cur;
v[j].PB(MP(t[j-1][y],sp[y]));
vt[j].PB(t[j][y]);
}
}
return;
}
long long arrival_time(long long Y){
vector<ll> nt;nt.PB(Y);
for(int j=1;j<m;j++){
pair<ll,ll> p={nt[j-1],-spn};
auto up=upper_bound(v[j].begin(),v[j].end(),p);
int pos=up-v[j].begin()-1;
ll ne=nt[j-1]+(len[j]-len[j-1])*spn;
if(pos==-1)nt.PB(ne);
else nt.PB(max(ne,vt[j][pos]));
}
return nt[m-1];
}
