#include "overtaking.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
using tp = tuple<ll, ll, ll>;
const int N = 1005;
ll l, n, m, x;
vector<ll> w, s;
vector<ll> t;
vector<vector<ll>> e, ct;
multiset<pii> ms[N];
struct blackslex {
struct info {
ll l, r, val;
info(ll l, ll r, ll val) : l(l), r(r), val(val) {}
constexpr friend bool operator < (const info &a, const info &b) {
return a.r < b.r;
}
};
ll lz;
multiset<info> ms;
void upd (ll l, ll r, ll val) {
val -= lz;
auto it = ms.lower_bound(info(0, l, 0));
if (it != ms.end() && it->l < l) {
auto cval = *it; ms.erase(it);
// cval->l < l <= cval->r
// split to [cval->l, l) and [l, cval->r]
ms.emplace(cval.l, l - 1, cval.val);
it = ms.emplace(l, cval.r, cval.val);
}
// !!!
for (; it != ms.end() && it->r <= r;) it = ms.erase(it);
// it->l <= r < it->r
// r < it->l
if (it != ms.end() && it->l <= r) {
auto cval = *it; ms.erase(it);
// ms.emplace(cval.l, r, cval.val);
ms.emplace(r + 1, cval.r, cval.val);
}
ms.emplace(l, r, val);
}
ll qr (ll x) {
auto it = ms.lower_bound(info(0, x, 0));
// x <= it->r
return (it == ms.end() || it->l > x ? x : it->val) + lz;
}
} oo;
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; n = N; t = T; x = X; m = M;
w.resize(n); s.resize(m);
for (int i = 0; i < n; i++) w[i] = W[i];
for (int i = 0; i < m; i++) s[i] = S[i];
e = vector<vector<ll>>(n, vector<ll>(m));
ct = vector<vector<ll>>(n, vector<ll>(m));
for (int i = 0; i < n; i++) ct[i][0] = t[i];
for (int j = 1; j < m; j++) {
map<ll, vector<ll>> mp;
ll cmx = 0;
for (int i = 0; i < n; i++) {
e[i][j] = ct[i][j - 1] + w[i] * (s[j] - s[j - 1]);
mp[ct[i][j - 1]].emplace_back(i);
}
for (auto &[x, y]: mp) {
for (auto &E: y) ct[E][j] = max(e[E][j], cmx);
for (auto &E: y) cmx = max(cmx, e[E][j]);
}
vector<tp> c;
// transition f_{j-1}(t) to f_j(t)
for (int i = 0; i < n; i++) {
ll st = ct[i][j - 1], ed = ct[i][j];
ll mx = ed - x * (s[j] - s[j - 1]);
ll mn = st + 1;
if (mx < mn) continue;
// start at t \in [tl, tr] -> oo.qr(t) \in [mn, mx]
// t + speed * dist
auto bs = [&] (ll rval) {
ll l = 0, r = 1e18 + 1;
while (l < r) {
ll mid = (l + r) >> 1LL;
auto ck = [&] (ll val) {
return oo.qr(val) >= rval;
};
if (ck(mid)) r = mid;
else l = mid + 1;
}
return l;
};
ll tl = bs(mn), tr = bs(mx + 1) - 1;
if (tl > tr) continue;
c.emplace_back(tl, tr, ed);
}
oo.lz += x * (s[j] - s[j - 1]);
sort(c.begin(), c.end(), [&] (const tp &a, const tp &b) {
return (get<1>(a) < get<1>(b));
});
for (auto &[x, y, z]: c) oo.upd(x, y, z);
}
return;
}
long long arrival_time(long long Y){
return oo.qr(Y);
}
