#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<pair<pair<int,int>, int>> e(n);
for (int j = 0; j < n; j++) {
e[j]={{t[i-1][j].first,t[i-1][j].first+(w[j]*dist)},j};
}
sort(e.begin(),e.end());
for (int k = 0; k < n; k++) {
if(k>0) e[k].first.second=max(e[k].first.second, e[k-1].first.second);
t[i][e[k].second].first=e[k].first.second;
}
for (int j = 0; j < n; j++) t[i-1][j].second=t[i][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;
}
