#include "overtaking.h"
#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
using namespace std;
const int inf = 2e18;
int M,X,N;
vi S;
vector<vi> t;
vector<vi> vects;
vector<vi> order;
void init(signed L, signed N_, std::vector<int> T, std::vector<signed> W, signed X_, signed M_, std::vector<signed> S_)
{
S = vi(all(S_));
X = X_;
M = M_;
N = N_;
order.resize(M);
vects.resize(M);
t.assign(M,vi(N,inf));
for (int i = 0;i<N;i++) t[0][i] = T[i];
for (int i = 0;i<M;i++) {
order[i] = vi(N);
iota(all(order[i]),0ll);
}
sort(all(order[0]),[&](int a,int b) {
return pii{t[0][a],W[a]} < pii{t[0][b],W[b]};
});
for (int i=1;i<M;i++) {
int worst = 0;
for (auto it : order[i-1]) {
worst = max(worst,t[i-1][it]+(S[i]-S[i-1])*W[it]);
t[i][it] = worst;
vects[i-1].push_back(t[i][it]);
}
sort(all(order[i]),[&](int a,int b) {
return pii{t[i][a],W[a]} < pii{t[i][b],W[b]};
});
}
return;
}
int before(int station,int tm) {
//buraya t'den < gelenlerin bi sonrakine gidiş maxı
int l = 1;
int r = vects[station].size();
while (l<=r) {
int m = (l+r) >> 1;
if (t[station][order[station][m-1]] < tm) l = m+1;
else r = m-1;
}
if (!r) return 0;
return vects[station][r-1];
}
int arrival_time(int Y)
{
int curt = Y;
for (int i = 0;i<M-1;i++) {
curt = max(curt+(S[i+1]-S[i])*X,before(i,curt));
}
return curt;
}
