#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<vector<ll>> t;
vector<ll> w;
vector<int> s;
vector<vector<int>> all;
int n, x;
void init(int L, int N, vector<ll> T, vector<int> W, int X, int M,
vector<int> S) {
s = S;
x = X;
t.resize(M);
for (int i = 0; i < N; i++) {
if (W[i] > X) {
w.push_back(W[i]);
t[0].push_back(T[i]);
}
}
n = w.size();
all.resize(M);
all[0].resize(n);
iota(all[0].begin(), all[0].end(), 0);
sort(all[0].begin(), all[0].end(), [&](int a, int b) {
if (t[0][a] != t[0][b])
return t[0][a] < t[0][b];
return w[a] < w[b];
});
for (int i = 1; i < M; i++) {
t[i].resize(n);
for (int j = 0; j < n; j++) {
t[i][j] = t[i - 1][j] + (s[i] - s[i - 1]) * w[j];
}
for (int j = 1; j < n; j++) {
t[i][all[i - 1][j]] = max(t[i][all[i - 1][j]], t[i][all[i - 1][j - 1]]);
}
all[i] = all[i - 1];
sort(all[i].begin(), all[i].end(), [&](int a, int b) {
if (t[i][a] != t[i][b])
return t[i][a] < t[i][b];
return w[a] < w[b];
});
}
w.push_back(x);
}
ll arrival_time(ll Y) {
t[0].push_back(Y);
n++;
assert(t[0].size() == w.size());
ll ta = Y;
for (int i = 1; i < s.size(); i++) {
ta += (s[i] - s[i - 1]) * x;
auto cmp = [&](int in1, int in2) { return t[i - 1][in1] < t[i - 1][in2]; };
int in =
lower_bound(all[i].begin(), all[i].end(), n - 1, cmp) - all[i].begin();
if (in > 0) {
ta = max(ta, t[i][all[i][in - 1]]);
}
t[i].push_back(ta);
}
n--;
for (int i = 0; i < t.size(); i++)
t[i].pop_back();
return ta;
}
