#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int N, L;
vector<int> W, S;
int X, M;
vector<ll> T;
ll expected[1001][1001];
vector<int> tot_ord[1001];
int pos[1001][1001];
map<ll, ll> mp;
ll shift = 0;
ll query(ll x) {
x += shift;
auto it = mp.upper_bound(x);
if (it != begin(mp)) x = max(x, prev(it)->second);
return x;
}
void merge(ll x, ll y) {
x += shift;
auto it = mp.upper_bound(x);
if (it != begin(mp) && prev(it)->second >= y) return;
mp[x] = y;
it = mp.find(x);
while (next(it) != mp.end() && next(it)->second <= y) mp.erase(next(it));
}
void init(int _L, int _N, std::vector<long long> _T, std::vector<int> _W, int _X, int _M, std::vector<int> _S)
{
L = _L;
M = _M;
N = _N;
T = _T;
W = _W;
X = _X;
S = _S;
// W.push_back(X);
// vector<vector<ll>> exp(N, vector<ll>(M));
vector<int> ord(N);
iota(begin(ord), end(ord), 0);
for (int i = 0; i < N; ++i) {
expected[i][0] = T[i];
}
for (int j = 1; j < M; ++j) {
sort(begin(ord), end(ord), [&](int x, int y){
if (expected[x][j - 1] != expected[y][j - 1]) return expected[x][j - 1] < expected[y][j - 1];
return W[x] < W[y];
});
tot_ord[j - 1] = ord;
ll tim = -1;
for (int it = 0; it < N; ++it) {
int i = ord[it];
pos[j - 1][i] = it;
// cerr << W[i] << " ";
expected[i][j] = expected[i][j - 1] + 1LL * W[i] * (S[j] - S[j - 1]);
expected[i][j] = max(tim, expected[i][j]);
tim = max(expected[i][j], tim);
}
// cerr << endl;
if (j == M - 1) {
sort(begin(ord), end(ord), [&](int x, int y){
if (expected[x][j - 1] != expected[y][j - 1]) return expected[x][j - 1] < expected[y][j - 1];
return W[x] < W[y];
});
tot_ord[j] = ord;
for (int it = 0; it < N; ++it) {
int i = ord[it];
pos[j][i] = it;
}
}
}
// for (int i = 0; i < M; ++i) {
// for (int j = 0; j < N; ++j) {
// cerr << expected[j][i] << " ";
// }
// cerr << "\n";
// }
// cerr << "\nDone!\n";
for (int i = M - 2; i >= 0; --i) {
vector<array<ll, 2>> a;
for (int it = 0; it < N; ++it) {
// int i1 = tot_ord[i - 1][it];
// int i2 = tot_ord[i][it];
// int v = tot_ord[i - 1][it];
ll e1 = expected[it][i];
ll e2 = expected[it][i + 1];
// cerr << e1 << " " << e2 << "\n";
a.push_back({e1, query(e2)});
}
shift += 1LL * X * (S[i + 1] - S[i]);
for (auto& [x, y] : a) {
merge(x + 1, y);
}
// for (auto& [x, y] : mp) {
// cerr << x << " " << y << "\n";
// }
// cerr << "\n";
}
}
long long arrival_time(long long Y)
{
return query(Y);
}
