#include "bits/stdc++.h"
using namespace std;
#define int long long
vector<array<int,4>> all;
void init(int32_t L, int32_t N,vector<long long> T,vector<int32_t> W, int32_t X, int32_t M,vector<int32_t>S){
//cout<<"hhh"<<endl;
vector<pair<int ,int>> v;
for(int i = 0;i<N;i++){
v.push_back({T[i],W[i]});
}
sort(v.begin(),v.end());
vector<array<int,4>> rngs;
int la = -1e18;
for(int i = 0;i<v.size();i++){
if(v[i].first>=la){
if(v[i].first!=la){
rngs.push_back({la,v[i].first-1,la-1,v[i].first-1});
rngs.push_back({v[i].first,v[i].first,v[i].first,v[i].first});
}
else{
rngs.push_back({la,v[i].first,la,v[i].first});
}
la = v[i].first+1;
}
}
rngs.push_back({la,1000000000000000000,la,1000000000000000000});
//cout<<"hhh"<<endl;
for(int i = 0;i<M-1;i++){
//cout<<"bb"<<endl;
sort(v.begin(),v.end());
sort(rngs.begin(),rngs.end());
int la =-1e18 , it = 0;
vector<pair<int,int>> nv;
vector<array<int,4>> nrngs;
int slow = -1e18;
for(int j = 0;j<rngs.size();j++){
while(it<v.size()&&((rngs[j][2]!=rngs[j][3]&&v[it]<make_pair(rngs[j][2],(long long)1000000000))||(rngs[j][2]==rngs[j][3]&&v[it]<make_pair(rngs[j][2],(long long)X)))){
int sh = v[it].first+(S[i+1]-S[i])*v[it].second;
sh = max(sh,slow);
slow = max(slow,sh);
nv.push_back({sh,v[it].second});
it++;
}
int dist = (S[i+1]-S[i])*X;
if(rngs[j][2]==rngs[j][3]){
nrngs.push_back({rngs[j][0],rngs[j][1],max(slow,rngs[j][2]+dist),max(slow,rngs[j][2]+dist)});
continue;
}
int L = rngs[j][2];
int R = (slow-dist);
R = min(R,rngs[j][3]);
if(R>=L){
nrngs.push_back({rngs[j][0],rngs[j][0]+(R-L),slow,slow});
}
R++;
R = max(R,rngs[j][2]);
if(R<=rngs[j][3]){
if(R<rngs[j][3]){
nrngs.push_back({rngs[j][0]+(R-L),rngs[j][1]-1,R+dist,rngs[j][3]+dist-1});
nrngs.push_back({rngs[j][1],rngs[j][1],rngs[j][3]+dist,rngs[j][3]+dist});
}else nrngs.push_back({rngs[j][0]+(R-L),rngs[j][1],R+dist,rngs[j][3]+dist});
}
}
while(it<v.size()){
int sh = v[it].first+(S[i+1]-S[i])*v[it].second;
sh = max(sh,slow);
slow = max(slow,sh);
nv.push_back({slow,v[it].second});
it++;
}
v = nv;
rngs = nrngs;
}all = rngs;
sort(all.begin(),all.end());
}
long long arrival_time(long long Y){
int l = 0 , r = all.size()-1 , ans = 0;
while(l<=r){
int mid = (l+r)/2;
if(all[mid][0]<=Y){
ans = mid;
l = mid+1;
}else r = mid-1;
}
if(all[ans][2]==all[ans][3])return all[ans][2];
return all[ans][2]+(Y-all[ans][0]);
}
