#include "overtaking.h"
#include <bits/stdc++.h>
#define sz(x) (int)(x.size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define cmin(a, b) a = min(a, b)
#define cmax(a, b) a = max(a, b)
#define int long long
using namespace std;
vector<vector<int>> dp;
vector<signed> s;
vector<pair<int, int>> a;
vector<set<pair<pair<int, int>, int>>> t;
vector<vector<pair<int, pair<int, int>>>> pref, pref2;
int n, m, x, l;
void init(signed L, signed N, vector<int> T, vector<signed> W, signed X, signed M, vector<signed> S) {
l=L, n=N, m=M, x=X, s=S;
for (int i=0; i<n; i++) {
if (W[i]>x) a.pb({W[i], T[i]});
}
sort(rall(a)); n=sz(a);
dp.resize(n, vector<int>(m, 0)), t.resize(m);
vector<vector<int>> positions(n, vector<int>(m, 0));
for (int i=0; i<n; i++) {
int act=a[i].se;
for (int j=0; j<m-1; j++) {
auto lb=lower_bound(all(t[j]), mp(mp(act, -1LL), -1LL));
int prec=act;
if (lb==t[j].begin()) act+=a[i].fi*(s[j+1]-s[j]);
else {
lb--;
act=max(act+a[i].fi*(s[j+1]-s[j]), lb->fi.se);
}
t[j].insert({{prec, act}, i});
positions[i][j]=prec;
}
positions[i][m-1]=act;
}
for (int i=0; i<n; i++) dp[i][m-1]=positions[i][m-1];
pref.resize(m), pref2.resize(m);
for (int j=m-1; j>=0; j--) {
vector<pair<int, int>> v;
for (int i=0; i<n; i++) v.pb({positions[i][j], i});
sort(all(v));
int pos=-1, mxcur=-1, poscur=-1, lst=-1;
for (auto [act, i]: v) {
if (lst!=act) pos=poscur;
if (pos==-1) {
dp[i][j]=act+(l-s[j])*x;
}
else {
if (j!=m-1) dp[i][j]=max(act+(l-s[j])*x, dp[pos][j+1]);
}
t[j].insert({{act, positions[i][j+1]}, i});
if (positions[i][j+1]>mxcur) mxcur=positions[i][j+1], poscur=i;
lst=act;
pref[j].pb({act, {mxcur, poscur}});
pref2[j].pb({act, {mxcur, poscur}});
}
int mn=1e18; pos=-1;
for (int tt=n-1; tt>=0; tt--) {
int i=v[tt].se;
if (a[i].se<mn) mn=a[i].se, pos=i;
pref[j][tt].se={mn, pos};
}
}
}
int arrival_time(int y) {
if (!n) return (int)y+x*l;
int lo=1, r=m-1, ans=-1;
while (lo<=r) {
int mid=(lo+r)/2;
int act=y+x*s[mid];
auto lb=lower_bound(all(pref[mid]), mp(act, mp(-1LL, -1LL)));
if (lb!=pref[mid].end() && lb->se.fi<y) r=mid-1, ans=mid;
else lo=mid+1;
}
if (ans==-1) return (int)y+x*l;
auto lb=upper_bound(all(pref2[ans-1]), mp(y+x*s[ans-1], mp(-1LL, -1LL))); lb--;
return dp[lb->se.se][ans];
}
