#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1001;
#define MID ((l+r)/2)
ll n, t[N], w[N], m, s[N], tn;
ll z[N];
bool comp(ll a, ll b){
return z[a]<z[b];
}
pair<ll,ll> li[N][N];
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S){
n=N;
for(ll i=0; i<n; i++){
t[i]=T[i];
w[i]=W[i];
}
tn=X;
m=M;
for(ll i=0; i<m; i++){
s[i]=S[i];
}
ll x[n][m], e[n][m], idx[n];
for(ll i=0; i<n; i++){
x[i][0]=t[i];
idx[i]=i;
}
for(ll j=1; j<m; j++){
for(ll i=0; i<n; i++){
e[i][j]=x[i][j-1]+w[i]*(s[j]-s[j-1]);
z[i]=x[i][j-1];
}
sort(idx,idx+n,comp);
ll c=0, ans=0;
for(ll i=0; i<n; i++){
if(i>0 && x[idx[i]][j-1]>x[idx[i-1]][j-1]) ans=max(ans,c);
x[idx[i]][j]=max(e[idx[i]][j],ans);
c=max(c,e[idx[i]][j]);
}
}
for(ll j=0; j<m-1; j++){
for(ll i=0; i<n; i++){
li[j][i]={x[i][j],e[i][j+1]};
}
sort(li[j],li[j]+n);
for(ll i=1; i<n; i++){
li[j][i].second=max(li[j][i].second,li[j][i-1].second);
}
// cout<<"---"<<j<<"---"<<endl;
// for(ll i=0; i<n; i++){
// cout<<li[j][i].first<<" "<<li[j][i].second<<endl;
// }
// cout<<endl;
}
return;
}
long long arrival_time(long long Y){
ll curr=Y;
for(ll j=0; j<m-1; j++){
// cout<<curr<<endl;
ll l=0, r=n-1, pos=-1;
while(l<=r){
if(li[j][MID].first<curr){
pos=MID;
l=MID+1;
}
else r=MID-1;
}
// cout<<pos<<endl<<endl;
if(pos==-1) curr=curr+(s[j+1]-s[j])*tn;
else curr=max(curr+(s[j+1]-s[j])*tn,li[j][pos].second);
}
return curr;
}
