#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); }