#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
#define ff first
#define ss second
#define mid ((l+r)>>1)
const int MXN = 1003;
const ll MX = 1'000'000'001'000'000'003;
inline pll eval(pll f, ll x) { return pll(x+f.ff, f.ss); }
inline bool cmp(pll f, pll g) {
return (__int128_t)f.ff*g.ss <= (__int128_t)g.ff*f.ss;
}
inline pair<pll, int> min_(pair<pll, int> x, pair<pll, int> y) {
return cmp(x.ff, y.ff) ? x : y;
}
struct lichao {
lichao *lc, *rc;
pll f;
int id;
lichao(): lc(NULL), rc(NULL), f(pll(MX, 1)), id(-1) {}
lichao *cpy() {
lichao *v = new lichao();
v->lc = lc, v->rc = rc, v->f = f;
return v;
}
void del() {
if(lc) lc->del();
if(rc) rc->del();
delete this;
}
};
lichao *add(pll f, int id, lichao *vv, bool pers, ll l=0, ll r=MX) {
if(!vv) {
lichao *v = new lichao();
v->f = f;
v->id = id;
return v;
}
lichao *v = pers ? vv->cpy() : vv;
if(r-l == 1) {
if(cmp(eval(f, l), eval(v->f, l))) {
v->f = f;
v->id = id;
}
return v;
}
bool L = cmp(eval(f, l), eval(v->f, l));
bool M = cmp(eval(f, mid), eval(v->f, mid));
if(M) {
swap(f, v->f);
swap(id, v->id);
}
if(L==M) v->rc = add(f, id, v->rc, pers, mid, r);
else v->lc = add(f, id, v->lc, pers, l, mid);
return v;
}
pair<pll, int> get(ll x, lichao *v, ll l=0, ll r=MX) {
if(!v) return {{MX, 1}, -1};
return min_({eval(v->f, x), v->id}, x<mid ? get(x, v->lc, l, mid) : get(x, v->rc, mid, r));
}
int L, n, m, X, ord[MXN];
vector<ll> T;
vector<int> W, S;
ll t[MXN][MXN], e[MXN][MXN], dp[MXN][MXN];
lichao *root[MXN];
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_;
int ptr=0;
for(int i=0; i<n; i++)
if(W[i]>X) {
T[ptr] = T[i];
W[ptr++] = W[i];
}
n = ptr;
if(n==0) return;
for(int i=0; i<n; i++)
t[i][0] = T[i];
iota(ord, ord+n, 0);
for(int j=0; j+1<m; j++) {
sort(ord, ord+n, [&](int x, int y) {
return t[x][j] < t[y][j];
});
for(int i=0; i<n; i++)
e[i][j+1] = t[i][j] + 1ll*W[i]*(S[j+1]-S[j]);
ll mx = 0;
for(int l=0,r; l<n; ) {
r=l;
while(r+1<n && t[ord[r+1]][j]==t[ord[r]][j]) r++;
ll mx2=mx;
for(int i=l; i<=r; i++)
mx2 = max(mx2, e[ord[i]][j+1]),
t[ord[i]][j+1] = max(e[ord[i]][j+1], mx);
mx = mx2;
l=r+1;
}
}
// for(int i=0; i<n; i++) {
// cout << t[i][0] << ' ';
// for(int j=1; j<m; j++) {
// cout << e[i][j] << ' ' << t[i][j] << ' ';
// }
// cout << '\n';
// }
// cout << '\n';
for(int j=m-2; j>=0; j--) {
sort(ord, ord+n, [&](int x, int y) {
return t[x][j] < t[y][j];
});
lichao *ds = NULL;
for(int i=0; i<n; i++) {
if(t[ord[i]][j]>t[ord[0]][j]) {
auto x = get(t[ord[i]][j], ds);
// cout << ord[i] << ' ' << j << ": " << t[ord[i]][j] << ' ' << x.ff.ff << ' ' << x.ff.ss << ' ' << x.ss << '\n';
ll up = x.ff.ff, dw = x.ff.ss;
int pos = lower_bound(S.begin(), S.end(),
S[j]+(up+dw-1)/dw)-S.begin();
if(pos==m)
dp[ord[i]][j] = 1ll*X*(L-S[j]);
else
dp[ord[i]][j] = t[x.ss][pos]-t[ord[i]][j]
+ dp[x.ss][pos];
}
else
dp[ord[i]][j] = 1ll*X*(L-S[j]);
ds = add({-t[ord[i]][j], W[ord[i]]-X}, ord[i], ds, 0);
}
ds->del();
}
sort(ord, ord+n, [&](int i, int j) {
return t[i][0] < t[j][0];
});
lichao *ds = NULL;
for(int i=0; i<n; i++)
root[i] = ds = add({-t[ord[i]][0], W[ord[i]]-X}, ord[i], ds, 1);
// for(int i=0; i<n; i++) cout << T[i] << ' ' << W[i] << '\n';
// for(int i=0; i<n; i++) {
// for(int j=0; j<m; j++)
// cout << dp[i][j] << ' ';
// cout << '\n';
// }
}
ll arrival_time(ll Y) {
if(n==0 || t[ord[0]][0]>=Y) return Y + 1ll*X*L;
int l=0, r=n;
while(r-l>1)
(t[ord[mid]][0]<Y ? l : r) = mid;
auto x = get(Y, root[l]);
ll up = x.ff.ff, dw = x.ff.ss;
int pos = lower_bound(S.begin(), S.end(),
(up+dw-1)/dw)-S.begin();
if(pos==m) return Y + 1ll*X*L;
return t[x.ss][pos] + dp[x.ss][pos];
}
