#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];
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);
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});
}
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);
}
}
ll arrival_time(ll Y)
{
ll ret = Y;
for(ll i = 0 ; i < m - 1 ; i++)
{
ll l = 0, r = (ll)vv[i].size() - 1;
while(l <= r)
{
ll mid = (l + r) >> 1;
if(vv[i][mid].fi <= ret)
l = mid + 1;
else
r = mid - 1;
}
if(vv[i][r].se == -1)
ret += (s[i + 1] - s[i]) * x;
else
ret = vv[i][r].se;
}
return ret;
}
