#include "overtaking.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
int l,x,n,m;
vector<vector<ll>>t,e;
vector<int>w,s;
struct segtree{
int size=1;
vector<ll>maxs;
void init(int n){
while(size<n)size*=2;
maxs.resize(2*size-1,-1);
}
void update(int i,ll v,int x,int lx,int rx){
if(rx-lx==1){
maxs[x]=v;
return;
}
int mid=(lx+rx)/2;
if(i<mid)update(i,v,2*x+1,lx,mid);
else update(i,v,2*x+2,mid,rx);
maxs[x]=max(maxs[2*x+1],maxs[2*x+2]);
}
void update(int i,ll v){
update(i,v,0,0,size);
}
void get(int l,int r,int x,int lx,int rx,ll& ans){
if(lx>=r || rx<=l)return;
if(lx>=l && rx<=r){
ans=max(ans,maxs[x]);
return;
}
int mid=(lx+rx)/2;
get(l,r,2*x+1,lx,mid,ans);
get(l,r,2*x+2,mid,rx,ans);
}
void get(int l,int r,ll& ans){
get(l,r,0,0,size,ans);
}
void print(){
for(int i=0;i<2*size-1;i++){
if(maxs[i]>-1)cout<<maxs[i]<<' ';
}
cout<<endl;
}
};
void init(int L, int N, vector<long long> T, vector<int> W, int X, int M, vector<int> S)
{
l=L,x=X,n=N,m=M;
w=W,s=S;
t.resize(n+1,vector<ll>(m));
e.resize(n+1,vector<ll>(m));
for(int i=0;i<n;i++){
t[i][0]=T[i];
}
segtree st;
st.init(n);
for(int stop=1;stop<m;stop++){
vector<pair<ll,int>>bef;
for(int i=0;i<n;i++){
e[i][stop]=t[i][stop-1]+((W[i]*1LL)*(S[stop]-S[stop-1]));
bef.pb({t[i][stop-1],i});
}
sort(bef.begin(),bef.end());
for(int i=0;i<n;i++){
st.update(i,e[bef[i].second][stop]);
}
for(int i=0;i<n;i++){
int l=-1,r=n;
while(l+1<r){
int mid=(l+r)/2;
if(bef[mid].first<t[i][stop-1])l=mid;
else r=mid;
}
ll ans=e[i][stop];
st.get(0,r,ans);
t[i][stop]=ans;
}
}
return;
}
long long arrival_time(long long Y){
vector<vector<ll>>T(n+1,vector<ll>(m)),E(n+1,vector<ll>(m));
T=t,E=e;
T[n][0]=Y;
segtree st2;
st2.init(n+1);
for(int stop=1;stop<m;stop++){
E[n][stop]=T[n][stop-1]+((x*1LL)*(s[stop]-s[stop-1]));
vector<pair<ll,int>>bef;
for(int i=0;i<=n;i++){
bef.pb({T[i][stop-1],i});
}
sort(bef.begin(),bef.end());
bool ok=0;
for(int i=0;i<=n;i++){
st2.update(i,E[bef[i].second][stop]);
if(ok){
for(int j=i;j<=n;j++){
int te=bef[j].second;
if(T[n][stop-1]<T[te][stop-1]){
// E[te][stop]=T[te][stop-1]+((w[te]*1LL)*(s[stop]-s[stop-1]));
T[te][stop]=max(T[te][stop],E[n][stop]);
}
}
break;
}
if(bef[i].second!=n)continue;
ok=1;
int l=-1,r=i+1;
while(l+1<r){
int mid=(l+r)/2;
if(bef[mid].first<T[n][stop-1])l=mid;
else r=mid;
}
ll ans=E[n][stop];
st2.get(0,r,ans);
T[n][stop]=ans;
}
}
// cout<<"E: "<<endl;
// for(int stop=1;stop<m;stop++){
// for(int i=0;i<=n;i++){
// cout<<E[i][stop]<<' ';
// }cout<<endl;
// }
// cout<<endl<<"T: "<<endl;
// for(int stop=1;stop<m;stop++){
// for(int i=0;i<=n;i++){
// cout<<T[i][stop]<<' ';
// }cout<<endl;
// }
return T[n][m-1];
}
// int main(){
// int n,l,x,m;
// cin>>l>>n>>x>>m;
// vector<int>s(m+1),w(n+1);
// vector<ll>t(n+1);
// for(int i=0;i<n;i++)cin>>t[i];
// for(int i=0;i<n;i++)cin>>w[i];
// for(int i=0;i<m;i++)cin>>s[i];
// init(l,n,t,w,x,m,s);
// cout<<arrival_time(50)<<endl;
// return 0;
// }
