#include "overtaking.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int N, M, X;
vector<int> S;
vector<vector<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(N, vector<ll>(N));
for (int i=0; i<N; i++) E[i][0] = 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[i][j-1], W[i]}, i});
sort(v.begin(), v.end());
for (auto [dc, i] : v){
ll exp = E[i][j-1]+(ll)W[i]*(ll)(S[j]-S[j-1]);
cur = max(cur, exp);
E[i][j] = cur;
}
}
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]);
for (int i=0; i<N; i++){
if (E[i][j-1] < cur) next = max(next, E[i][j]);
}
cur = next;
}
return cur;
}
