#include "overtaking.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int N, M, X;
vector<int> S;
vector<vector<pair<ll,ll>>> E;
void init(int L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> S){
::N = N;
::M = M;
::X = X;
::S = S;
E.resize(M, vector<pair<ll,ll>>(N));
for (int i=0; i<N; i++) E[0][i].first = T[i];
for (int j=1; j<M; j++){
ll cur = 0;
vector<pair<pair<ll,ll>,int>> v;
for (int i=0; i<N; i++) v.push_back({{E[j-1][i].first, W[i]}, i});
sort(v.begin(), v.end());
for (auto [dc, i] : v){
ll exp = E[j-1][i].first+(ll)W[i]*(ll)(S[j]-S[j-1]);
cur = max(cur, exp);
E[j][i].first = cur;
}
}
for (int i=0; i<N; i++){
for (int j=0; j<M-1; j++) E[j][i].second = E[j+1][i].first;
}
for (int j=0; j<M-1; j++){
sort(E[j].begin(), E[j].end());
for (int i=1; i<N; i++) E[j][i].second = max(E[j][i].second, E[j][i-1].second);
}
return;
}
ll arrival_time(ll Y){
ll cur = Y;
for (int j=1; j<M; j++){
ll next = cur+(ll)X*(ll)(S[j]-S[j-1]);
int l = -1, r = N;
while (l < r-1){
int mid = (l+r)/2;
if (E[j-1][mid].first < cur) l = mid;
else r = mid;
}
if (l != -1) next = max(next, E[j-1][l].second);
cur = next;
}
return cur;
}
