#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using vi = vector <int>;
const ll MAXN = 1E3+16;
ll l, n, x, m;
vll t[MAXN], e[MAXN];
vll prefM[MAXN];
vll ist[MAXN], is[MAXN];
vi w, s;
// bus i moves 1 km in w[i] s/km
void init (int L, int N, vll T, vi W, int X, int M, vi S) {
l = L; n = N; x = X; m = M;
t[0] = T;
w = W; s = S;
for (ll i = 1; i < m; i++) {
ll dis = s[i]-s[i-1];
e[i].assign(n, -15);
for (ll j = 0; j < n; j++) {
e[i][j] = t[i-1][j] + dis*w[j];
}
t[i].assign(n, -15);
is[i].assign(n, -15);
iota(is[i].begin(), is[i].end(), 0);
sort(is[i].begin(), is[i].end(), [&](ll a, ll b) {
return t[i-1][a] < t[i-1][b];
});
ist[i].assign(n, -15);
for (ll j = 0; j < n; j++) {
ist[i][j] = t[i-1][is[i][j]];
}
prefM[i].assign(n, -15);
prefM[i][0] = e[i][is[i][0]];
for (ll j = 1; j < n; j++) {
prefM[i][j] = max(prefM[i][j-1], e[i][is[i][j]]);
}
for (ll j = 0; j < n; j++) {
ll idx = upper_bound(is[i].begin(), is[i].end(), t[i-1][j]-1, [&](ll a, ll b) {
return t[i-1][a] < t[i-1][b];
}) - is[i].begin()-1;
if (idx < 0) t[i][j] = e[i][j];
else t[i][j] = max(e[i][j], prefM[i][idx]);
}
}
}
ll arrival_time (ll y) {
for (ll i = 1; i < m; i++) {
ll dis = s[i]-s[i-1];
ll ey = y + dis*x;
ll idx = upper_bound(ist[i].begin(), ist[i].end(), y-1) - ist[i].begin()-1;
if (idx < 0) y = ey;
else y = max(ey, prefM[i][idx]);
}
return y;
}
