#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)rngs.push_back({la,v[i].first,la,v[i].first});
la = v[i].first;
}
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()&&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 = max(R,rngs[j][2]);
if(R<rngs[j][3]){
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;
}
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]);
}
/*signed main(){
init(6, 4, {20, 10, 40, 0}, {5, 20, 20, 30}, 10, 4, {0, 1, 3, 6});
cout<<arrival_time(50);
}*/
