#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define ll long long
#define ff first
#define ss second
const int N = 3005;
const ll INF = 1e18;
set<pair<ll, ll>> pref[N];
vector<ll> T, W, S;
ll n, m, x, L;
set<array<ll, 3>> SE;
ll tots = 0;
void init(int Ll, int nn, std::vector<long long> t, std::vector<int> w, int xx, int mm, std::vector<int> s)
{
L = Ll, n=nn, m=mm, x=xx;
for(int i = 0; i < n; ++i){
if(w[i] > x)
W.pb(w[i]), T.pb(t[i]);
}
for(int f: s) S.pb(f);
--m;
n = W.size();
vector<pair<ll, int>> F;
for(int i =0; i < n; ++i) F.pb({W[i], i});
sort(all(F));
reverse(all(F));
vector<vector<ll>> dp(n + 1, vector<ll>(m + 2));
for(int i = 0; i < n; ++i){
dp[i][0] = T[F[i].ss];
for(int j = 1; j <= m; ++j){
ll mx = dp[i][j - 1] + F[i].ff * (S[j] - S[j-1]);
auto pos = pref[j].lower_bound(pair<ll,ll>{dp[i][j - 1], -1});
if(pos == pref[j].begin()){
dp[i][j] = mx;
}else{
pos = prev(pos);
dp[i][j] = max(mx, (*pos).ss);
}
pref[j].insert({dp[i][j - 1], dp[i][j]});
}
}
// for(int i = 1; i <= m; ++i){
// for(auto p: pref[i]) cout << p.ff << ' ' << p.ss << '\n';
// cout << '\n';
// }
// cout<<"c\n";
vector<vector<array<ll, 3>>> ss(m + 1);
for(int i = 1; i <= m; ++i){
tots += S[i] - S[i - 1];
for(auto p: pref[i]){
p.ff++;
if(p.ss - x * (S[i] - S[i - 1]) >= p.ff){
ss[i].pb({p.ff - x * (tots - (S[i] - S[i-1])), p.ss - x * tots, p.ss + (L-tots) * x});
}
}
sort(all(ss[i]));
for(int j = int(ss[i].size()) - 2; j >= 0; --j){
ss[i][j][1] = min(ss[i][j][1], ss[i][j + 1][0] - 1);
}
// cout << x * tots << '\n';
// for(auto x: ss[i]){
// cout << x[0] << ' ' << x[1] << ' ' << x[2] << '\n';
// }
// cout << endl;
}
// cout << "good " << endl;
SE.insert({-INF, INF, -1});
for(int j = m; j >= 1; --j){
for(auto p: ss[j]){
ll l = p[0], r = p[1], to = p[2];
if(r < l) continue;
ll l2 = -1, r2 = -1;
auto it = SE.lower_bound(array<ll,3>{l, -1, 0});
while(it != SE.end() && (*it)[0] <= r){
auto f = *it;
auto it2 = next(it);
// cout << f[1] << "wtf";
if(f[1] >= r){
if(f[2] != -1){
to = max(to, f[2]);
}else{
if(it2 == SE.end()){
// r + 1, inf, -1
// r + 1, tooo, -1
// cout << "wtf" << endl;
l2 = r + 1;
r2 = INF;
}else{
l2 = r + 1;
r2 = (*it2)[0] - 1;
}
}
}
// cout << "wtf" << endl;
SE.erase(it);
it = SE.lower_bound(array<ll,3>{l, -1, 0});
}
if(l2 != -1) SE.insert({l2, r2, -1});
// for(auto x: SE){
// cout << x[0] << ' ' << x[1] << ' ' << x[2] << '\n';
// }
// cout << j << " phase " << l << ' ' << r << ' ' << to << endl;
it = SE.lower_bound(array<ll,3>{l, -1, 0});
if(it != SE.begin()){
auto f = *prev(it);
if(f[1] >= l){
if(f[1] == r){
to = max(to, f[2]);
}
SE.erase(prev(it));
if(f[0] <= l - 1)
SE.insert({f[0], l - 1, f[2]});
}
}
SE.insert({l, r, to});
if((*prev(SE.end()))[1] < INF){
SE.insert({(*prev(SE.end()))[1] + 1, INF, -1});
}
// for(auto x: SE){
// cout << x[0] << ' ' << x[1] << ' ' << x[2] << '\n';
// }
// cout << j << " phase " << l << ' ' << r << ' ' << to << endl;
// cout << '\n';
}
}
return;
}
long long arrival_time(long long Y)
{
// ll cur = Y;
// for(int j = 1; j <= m; ++j){
// ll mx = cur + x * (S[j] - S[j-1]);
// auto pos = pref[j].lower_bound(pair<ll,ll>{cur, -1});
// if(pos == pref[j].begin()){
// cur = mx;
// }else{
// pos = prev(pos);
// cur = max(mx, (*pos).ss);
// }
// }
auto it = SE.lower_bound(array<ll,3>{Y, INF+1, INF});
--it;
if((*it)[2] == -1) return Y + x * L;
return (*it)[2];
}
