#include "overtaking.h"
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#define GO(l,r) (sped*(dis[r]-dis[l]))
typedef long long ll;
map<ll,ll> station[1010];
#define MP make_pair
vector<ll> dis;
unordered_map<ll,ll>memo[1010];
ll dp[1010][1010],XTH[1010][1010],pos[1010][1010];
ll sped;
ll st[1010][1010];
int M,N2;
inline int onezsmaller(int station,ll T){
return lower_bound(XTH[station],XTH[station]+N2+1,T)-XTH[station]-1;
}
void init(int L, int N, vector<ll> T, vector<int> W, int X, int M_, vector<int> S){
for(auto i:S)dis.push_back(i);
sped=X;
M=M_;
for(int i=1;i<=N;i++)
dp[i][0]=T[i-1];
int x=clock();
for(int j=1;j<M;j++) {for(int i=1;i<=N;i++)
dp[i][j]=dp[i][j-1]+(dis[j]-dis[j-1])*W[i-1];
vector<int>V(N);
iota(V.begin(),V.end(),1);
sort(V.begin(),V.end(),[j](int a,int b){
return dp[a][j-1]-dp[b][j-1]?dp[a][j-1]<dp[b][j-1]:dp[a][j]<dp[b][j];
});
ll prv=0;
for(auto i:V) {
prv=dp[i][j]=max(dp[i][j],prv);
if(W[i-1]>X)
station[j-1][dp[i][j-1]]=dp[i][j];
}
}
int y=clock();
for(int i=1;i<=N;i++)
if(W[i-1]>X) { N2++;
for(int j=0;j<M;j++)
st[j][N2]=dp[i][j];
}
for(int i=0;i<M;i++)
st[i][0]=-1,
sort(st[i],st[i]+N2+1);
for(int i=0;i<M;i++)
for(int j=0;j<=N2;j++)
XTH[i][j]=st[i][j];
for(int j=0;j<M-1;j++)
station[j][-1]=0;
cerr<<(y-x)/1.0/CLOCKS_PER_SEC<<'\n';
}
ll CCCALC(int STA,ll T){
int ST=STA;
ll org=T;
if(memo[ST][T])
return memo[ST][T];
int C=onezsmaller(ST,T);
if(C==onezsmaller(M-1,GO(ST,M-1)+T))
return GO(ST,M-1)+T;
int l=ST,r=M-1,res=-1;
while(l<=r){
int mid=l+r>>1;
if(XTH[mid][C]<GO(ST,mid)+T)
l=mid+1,res=mid;
else r=mid-1;
}
assert(res>=0);
T+=GO(ST,res);
ST=res;
return memo[STA][org]=CCCALC(res+1,(--station[res].lower_bound(T))->second);
}
int ans,CC;
ll arrival_time(ll Y){
ll res= CCCALC(0,Y);
return res;
}
