#include <vector>
#include <map>
#include <iostream>
using namespace std;
int const N=1010,M=1010;
long long reach[N][M]={};
int n,m;
long long st[N],sp[N];
int stops[N];
map<int,vector<pair<long long,long long>>>mx;
void comp()
{
map<long long,vector<int>>d;
for (int i=0;i<n;i++)
{
reach[i][0]=st[i];
d[st[i]].push_back(i);
}
for (int i=1;i<m;i++)
{
long long pre=0;
for (auto j:d)
{
long long mn=0;
for (auto k:j.second)
{
reach[k][i]=reach[k][i-1]+sp[k]*(stops[i]-stops[i-1]);
reach[k][i]=max(pre,reach[k][i]);
mn=max(mn,reach[k][i]);
}
pre=max(pre,mn);
mx[i].push_back({j.first,pre});
}
d.clear();
for (int j=0;j<n;j++)
d[reach[j][i]].push_back(j);
}
}
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=0;i<n;i++)
st[i]=T[i];
for (int i=0;i<n;i++)
sp[i]=W[i];
for (int i=0;i<m;i++)
stops[i]=S[i];
sp[n]=X;
comp();
}
long long arrival_time(long long Y)
{
long long cos=Y;
for (int i=1;i<m;i++)
{
long long cos1=cos+(stops[i]-stops[i-1])*sp[n];
pair<long long,long long>f={cos,-1};
int z=lower_bound(begin(mx[i]),end(mx[i]),f)-begin(mx[i]);
if (z!=0)
{
z--;
cos1=max(cos1,mx[i][z].second);
}
cos=cos1;
}
return cos;
}
