#include "overtaking.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int L, N, X, M;
vector<vector<ll>> e;
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;
e.resize(M);
for (int i = 0; i < M; i++) {
e[i].resize(N);
}
for (int i = 0; i < N; i++) {
e[0][i] = T[i];
}
for (int i = 1; i < M; i++) {
vector<pair<ll, int>> ord;
for (int j = 0; j < N; j++) {
ord.push_back({e[i - 1][j], j});
}
sort(ord.begin(), ord.end());
ll mx = 0, gg = 0;
for (int j = 0; j < N; j++) {
ll nw = ord[j].second;
e[i][nw] = max(mx, e[i - 1][nw] + W[nw] * (S[i] - S[i - 1]));
gg = max(gg, e[i][nw]);
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 (int i = 1; i < M; i++) {
ll nx = tim + X * (S[i] - S[i - 1]);
for (int j = 0; j < N; j++) {
if (e[i - 1][j] < tim)
nx = max(nx, e[i][j]);
}
tim = nx;
}
return tim;
}
