#include<bits/stdc++.h>
#define MAXN 1007
using namespace std;
int n,m;
int station[MAXN];
long long speed[MAXN],start[MAXN];
pair<long long,int> st[MAXN][MAXN];
long long maxtim[MAXN][MAXN];
long long arrive[MAXN][MAXN];
bool cmp(pair<long long,int> fr,pair<long long,int> sc){
if(fr.first!=sc.first)return fr.first<sc.first;
return speed[fr.second] < speed[sc.second];
}
void build_timetable(){
for(int i=1;i<=n;i++){
arrive[1][i]=start[i];
st[1][i]={start[i],i};
}
sort(st[1]+1,st[1]+n+1,cmp);
for(int i=2;i<=m;i++){
long long dist=station[i]-station[i-1];
for(int f=1;f<=n;f++){
int curr=st[i-1][f].second;
maxtim[i-1][f]=st[i-1][f].first + dist*speed[curr];
maxtim[i-1][f]=max(maxtim[i-1][f],maxtim[i-1][f-1]);
arrive[i][curr]=maxtim[i-1][f];
st[i][f]={arrive[i][curr],curr};
}
sort(st[i]+1,st[i]+n+1,cmp);
}
}
void init(int L, int N, vector<long long> T, vector<int> W, int X, int M, vector<int> S){
n=N; m=M;
for(int i=1;i<=m;i++)station[i]=S[i-1];
for(int i=1;i<=n;i++)speed[i]=W[i-1];
for(int i=1;i<=n;i++)start[i]=T[i-1];
int sm=0;
for(int i=1;i<=n;i++){
if(speed[i]<=X)continue;
sm++;
speed[sm]=speed[i];
start[sm]=start[i];
}
n=sm;
speed[n+1]=X;
build_timetable();
}
long long arrival_time(long long Y){
long long tim=Y;
for(int i=2;i<=m;i++){
long long dist=station[i]-station[i-1];
int l=0,r=n+1,tt;
while(l+1<r){
tt=(l+r)/2;
if(st[i-1][tt].first<tim){
l=tt;
}else{
r=tt;
}
}
tim=max(maxtim[i-1][l] , tim+speed[n+1]*dist);
}
return tim;
}
/*int main(){
init(6, 4, {20, 10, 40, 0}, {5, 20, 20, 30}, 10, 4, {0, 1, 3, 6});
cout<<arrival_time(0)<<"\n";
cout<<arrival_time(50)<<"\n";
return 0;
}*/
