#include "overtaking.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int L, N, X, M;
vector<vector<ll>> e;
vector<vector<pair<ll, ll>>> pp;
vector<ll> T;
vector<int> W, S;
void init(int L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> S) {
::L = L;
::N = N;
::T = T;
::W = W;
::X = X;
::M = M;
::S = S;
pp.resize(M);
e.resize(M);
for (ll i = 0; i < M; i++) {
e[i].resize(N);
pp[i].resize(N);
}
for (ll i = 0; i < N; i++) {
e[0][i] = T[i];
}
for (ll i = 1; i < M; i++) {
vector<pair<ll, ll>> ord;
for (ll j = 0; j < N; j++) {
ord.push_back({e[i - 1][j], j});
}
sort(ord.begin(), ord.end());
ll mx = 0, gg = 0;
for (ll j = 0; j < N; j++) {
ll nw = ord[j].second;
e[i][nw] = max(mx, e[i - 1][nw] + 1ll * W[nw] * (S[i] - S[i - 1]));
gg = max(gg, e[i][nw]);
pp[i][j] = {ord[j].first, e[i][nw]};
if (j)
pp[i][j].second = max(pp[i][j].second, pp[i][j - 1].second);
if (j < N - 1 && ord[j].first != ord[j + 1].first)
mx = max(mx, gg);
}
}
return;
}
ll arrival_time(ll Y) {
ll tim = Y;
for (ll i = 1; i < M; i++) {
ll nx = tim + 1ll * X * (S[i] - S[i - 1]);
// for (ll j = 0; j < N; j++) {
// if (e[i - 1][j] < tim)
// nx = max(nx, e[i][j]);
// }
auto it = lower_bound(pp[i].begin(), pp[i].end(), make_pair(tim, -1ll));
if (it == pp[i].begin())
tim = nx;
else
tim = max(nx, (--it)->second);
}
return tim;
}
