#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define modwwe int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task2 "top1apio"
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define mask(k) (1ll<<k)
#define checktime cerr << (double)clock() / CLOCK S_PER_SEC * 1000 << " ms";
using namespace std;
#define getchar_unlocked getchar
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
using i128 = __int128;
int rand(int l, int r)
{
return uniform_int_distribution<int>(l, r)(rd);
}
void phongbeo();
const ll inf = 1e15+7;
const int mod2 =998244353;
//const ll base=67;
ll n, m, s1, s2, s4, s3, sf, k, s5, s6, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2,r2, center;
ll i, s10, s12, k1, k2, k3, s11, lim, w, l, r, dem5, dem6, dem7, dem9, root, en;
ll el = 19;
map<ll,pair<ll,ll>>cnt;
struct ic
{
ll a,b,c;
};
bool cmp(ic a,ic b)
{
if(a.a==b.a)return a.b<b.b;
return a.a<b.a;
}
struct ib
{
ll a,b;
};
vector<ib> vc[1001];
ic d[1001];
bool okk=0;
ll get(ll x,ll y)
{
y-=x*k;
auto it=cnt.upper_bound(y);
if(it==cnt.begin())return y+lim*k;
it--;
ll xx=it->first;
if(cnt[xx].first>=y)return cnt[xx].second;
return y+lim*k;
}
void upd(ll l,ll r,ll cx,ll cy,ll x)
{
l-=cx*k;
r-=cy*k;
if(l>r)return;
while(true)
{
auto it=cnt.upper_bound(l);
if(it!=cnt.end())
{
ll xx=it->first;
pair<ll,ll> yy=cnt[xx];
if(xx<=r)
{
cnt.erase(xx);
if(r+1<=yy.first)
{
cnt[r+1]=yy;
break;
}
}
else
{
break;
}
}
else
{
break;
}
}
auto it=cnt.upper_bound(l);
if(it!=cnt.begin())
{
it--;
ll xx=it->first;
if(cnt[xx].first>r)cnt[r+1]=cnt[xx];
if(xx!=l&&cnt[xx].first>=l)cnt[xx].first=l-1;
}
cnt[l]= {r,x};
}
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
n=N;
m=M;
k=X;
lim=L;
for(int i=1; i<=n; i++)
d[i]= {T[i-1],W[i-1],i};
for(int i=0; i<m-1; i++)
{
sort(d+1,d+1+n,cmp);
s4=-inf;
for(int j=1; j<=n; j++)
{
if(d[j].a+1ll*(S[i+1]-S[i])*d[j].b>s4)
{
vc[i].pb({d[j].a,d[j].a+1ll*(S[i+1]-S[i])*d[j].b});
}
s4=max(s4,d[j].a+1ll*(S[i+1]-S[i])*d[j].b);
d[j].a=max(d[j].a,s4);
}
}
for(int i=m-2; i>=0; --i)
{
for(int j=0; j<vc[i].size(); j++)
{
ll g=vc[i][j].a;
ll gg=vc[i][j].b;
ll x=get(S[i+1],vc[i][j].b);
upd(g+1,gg,S[i],S[i+1],x);
}
}
}
long long arrival_time(long long y)
{
return get(0,y);
}
