#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 lll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
#define MAX 9223372036854775807LL
#define MIN -9223372036854775807LL
#define INF 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout << fixed; cout.precision(10);
#define sp << " "
#define en << "\n"
#define compress(v) sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end())
ll n, x, m;
ll t[1010];
ll w[1010];
ll cc;
pll a[1010][1010];
ll tmp[1010];
ll TM[1010][1010];
ll s[1010];
vector<pll> vv[1010];
vector<ll> num[1010];
struct gujo
{
ll L, R, ok, gap;
};
vector<gujo> ans;
void init(int L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> S)
{
n = N;
x = X;
m = M;
for(ll i = 0 ; i < n ; i++)
{
if(W[i] <= X)
continue;
t[cc] = T[i];
w[cc++] = W[i];
}
for(ll i = 0 ; i < m ; i++)
s[i] = S[i];
n = cc;
for(ll i = 0 ; i < n ; i++)
a[0][i] = {t[i], w[i]};
sort(a[0], a[0] + n);
ll ccc = 0;
for(ll i = 0 ; i < m - 1 ; i++)
{
vector<pll> vec, evec;
vector<ll> vec2;
ll dist = s[i + 1] - s[i];
for(ll j = 0 ; j < n ; j++)
{
ll TT = a[i][j].fi;
ll WW = a[i][j].se;
TM[i][j] = TT + WW * dist;
vec.push_back({TT + 1, j});
evec.push_back({TT + (WW - x) * dist, j});
vec2.push_back(TT + 1);
vec2.push_back(TT + (WW - x) * dist);
}
vec2.push_back(0);
sort(vec.begin(), vec.end());
sort(evec.begin(), evec.end());
compress(vec2);
multiset<ll> st;
ll p1 = 0, p2 = 0;
for(auto &j : vec2)
{
while(p1 < (ll)vec.size() && vec[p1].fi <= j)
{
st.insert(TM[i][vec[p1].se]);
p1++;
}
while(p2 < (ll)evec.size() && evec[p2].fi <= j)
{
st.erase(st.find(TM[i][evec[p2].se]));
p2++;
}
if(!st.empty())
vv[i].push_back({j, (*st.rbegin())});
else
vv[i].push_back({j, -1});
num[i].push_back(++ccc);
}
stack<pll> stk;
for(ll j = n - 1 ; j >= 0 ; j--)
{
while(!stk.empty() && stk.top().fi <= TM[i][j])
stk.pop();
stk.push({TM[i][j], j});
}
vector<ll> idx;
while(!stk.empty())
{
idx.push_back(stk.top().se);
stk.pop();
}
idx.push_back(n);
for(ll j = 0 ; j < (ll)idx.size() - 1 ; j++)
{
for(ll k = idx[j] ; k < idx[j + 1] ; k++)
tmp[k] = TM[i][idx[j]];
}
for(ll j = 0 ; j < n ; j++)
a[i + 1][j] = {tmp[j], a[i][j].se};
sort(a[i + 1], a[i + 1] + n);
}
/*cout << "vv\n";
for(ll i = 0 ; i < m - 1 ; i++)
{
cout << i en;
for(auto &j : vv[i])
cout << j.fi sp << j.se en;
}
cout en;*/
vector<gujo> vec;
for(ll i = 0 ; i < (ll)vv[m - 2].size() ; i++)
{
gujo tmp;
tmp.L = vv[m - 2][i].fi;
if(i == (ll)vv[m - 2].size() - 1)
tmp.R = INF;
else
tmp.R = vv[m - 2][i + 1].fi - 1;
if(vv[m - 2][i].se != -1)
tmp.ok = 1, tmp.gap = vv[m - 2][i].se;
else
tmp.ok = 0, tmp.gap = (s[m - 1] - s[m - 2]) * x;
vec.push_back(tmp);
}
/*for(auto &i : vec)
cout << i.L sp << i.R sp << i.ok sp << i.gap en;
cout << "OKOK\n";*/
for(ll i = m - 3 ; i >= 0 ; i--)
{
vector<gujo> tvec;
for(ll j = 0 ; j < (ll)vv[i].size() ; j++)
{
gujo tmp;
ll L = vv[i][j].fi;
ll R = 0;
if(j == (ll)vv[i].size() - 1)
R = INF;
else
R = vv[i][j + 1].fi - 1;
tmp.L = L, tmp.R = R;
if(vv[i][j].se != -1)
{
ll l = 0, r = (ll)vec.size() - 1;
while(l <= r)
{
ll mid = (l + r) >> 1;
if(vec[mid].L <= vv[i][j].se)
l = mid + 1;
else
r = mid - 1;
}
if(vec[r].ok)
tmp.ok = 1, tmp.gap = vec[r].gap;
else
tmp.ok = 1, tmp.gap = vv[i][j].se + vec[r].gap;
tvec.push_back(tmp);
continue;
}
L += (s[i + 1] - s[i]) * x;
R += (s[i + 1] - s[i]) * x;
ll l = 0, r = (ll)vec.size() - 1;
ll lidx, ridx;
while(l <= r)
{
ll mid = (l + r) >> 1;
if(vec[mid].L <= L)
l = mid + 1;
else
r = mid - 1;
}
lidx = r;
l = 0, r = (ll)vec.size() - 1;
while(l <= r)
{
ll mid = (l + r) >> 1;
if(vec[mid].L <= R)
l = mid + 1;
else
r = mid - 1;
}
ridx = r;
ll last = L;
for(ll k = lidx ; k <= ridx ; k++)
{
tmp.L = last - (s[i + 1] - s[i]) * x;
tmp.R = min(R, vec[k].R) - (s[i + 1] - s[i]) * x;
if(vec[k].ok)
tmp.ok = 1, tmp.gap = vec[k].gap;
else
tmp.ok = 0, tmp.gap = vec[k].gap + (s[i + 1] - s[i]) * x;
tvec.push_back(tmp);
last = vec[k].R + 1;
}
}
gujo tmp;
if(tvec.empty())
assert(0);
tmp = tvec[0];
vec.clear();
/*for(auto &i : tvec)
cout << i.L sp << i.R sp << i.ok sp << i.gap en;
cout << "TOKOK\n";*/
for(ll i = 1 ; i < (ll)tvec.size() ; i++)
{
if(tvec[i].ok == tmp.ok && tvec[i].gap == tmp.gap)
tmp.R = max(tmp.R, tvec[i].R);
else
{
vec.push_back(tmp);
tmp = tvec[i];
}
}
vec.push_back(tmp);
/*for(auto &i : vec)
cout << i.L sp << i.R sp << i.ok sp << i.gap en;
cout << "OKOK\n";*/
}
ans = vec;
}
ll arrival_time(ll Y)
{
ll l = 0, r = (ll)ans.size() - 1;
while(l <= r)
{
ll mid = (l + r) >> 1;
if(ans[mid].L <= Y)
l = mid + 1;
else
r = mid - 1;
}
if(!ans[r].ok)
return ans[r].gap + Y;
return ans[r].gap;
}
