#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
int l,n,x,m;
vector<vector<pair<int,int>>> t;
vector<int> s,w;
void init(signed L, signed N, std::vector<long long> T, std::vector<signed> W, signed X, signed M, std::vector<signed> S)
{
l=L;
n=N;
x=X;
m=M;
s.assign(S.begin(),S.end());
w.assign(W.begin(),W.end());
t.resize(m,vector<pair<int,int>>(n));
for (int i = 0; i < n; i++) t[0][i].first=T[i];
for (int i = 1; i < m; i++)
{
int dist=s[i]-s[i-1];
vector<int> e(n);
for (int j = 0; j < n; j++) e[j]=t[i-1][j].first+(w[j]*dist);
for (int j = 0; j < n; j++)
{
for (int k = 0; k < n; k++)
{
if(j==k) continue;
if(t[i-1][k].first<t[i-1][j].first){
e[j]=max(e[j],e[k]);
}
}
}
for (int k = 0; k <= n; k++) t[i][k].first=e[k];
}
for (int i = 0; i < m-1; i++) for (int j = 0; j < n; j++) t[i][j].second=t[i+1][j].first;
for (int i = 0; i < m; i++) sort(t[i].begin(),t[i].end());
return;
}
int lb(int i, int y){
int _l=0, _r=n-1;
int ans=-1;
while(_l<=_r){
int mid=_l+(_r-_l)/2;
if(t[i][mid].first<y) {
_l=mid+1;
ans=mid;
}
else _r=mid-1;
}
return ans;
}
long long arrival_time(long long Y)
{
for (int i = 1; i < m; i++)
{
int eY=Y+(x*(s[i]-s[i-1]));
int pos=lb(i-1,Y);
if(pos==-1) return Y+(x*(l-s[i-1]));
Y=max(eY,t[i][pos].first);
cerr << Y << "\n";
}
return Y;
}
