#include "overtaking.h"
#include<bits/stdc++.h>
using namespace std;
const long long inf=LLONG_MAX;
const int maxn=1e3+5;
#define pii pair<long long,long long>
#define fi first
#define se second
struct bus{
long long s,t;
int id;
bool operator<(bus o){
if(s!=o.s) return s<o.s;
else return t<o.t;
}
};
int M,N;
long long X,L;
vector<long long> T,S,W;
bus B[maxn][maxn];
void init(int l, int n, vector<long long> st, vector<int> w, int x, int m, vector<int> s)
{
L=l;N=n;X=x;M=m;T=st;
W.resize(N);S.resize(M);
for(int i=0;i<N;i++) W[i]=w[i];
for(int i=0;i<M;i++) S[i]=s[i];
for(int i=M-1;i>=1;i--) S[i]-=S[i-1];
for(int i=0;i<N;i++) B[0][i]={0,T[i],i};
for(int i=1;i<M;i++){
for(int j=0;j<N;j++){
auto [ss,tt,id]=B[i-1][j];
B[i][j]={tt,tt+S[i]*W[id],id};
}
sort(B[i],B[i]+N);
for(int j=1;j<N;j++) B[i][j].t=max(B[i][j].t,B[i][j-1].t);
}
}
long long arrival_time(long long cur)
{
for(int i=1;i<M;i++){
int l=0,r=N-1,pos=-1;
while(r>=l){
int mid=(l+r)>>1;
if(B[i][mid].s<cur) pos=mid,l=mid+1;
else r=mid-1;
}
cur=cur+X*S[i];
if(pos!=-1) cur=max(cur,B[i][pos].t);
}
return cur;
}
