//#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll SZ = 1001;
vector<vector<ll>> arrival(SZ+1, vector<ll>(SZ+1,-1)); //arrival[time][bus]
vector<vector<int>> sortOrders;
ll n, X_, M_;
vector<ll> t, w;
vector<ll> S_;
vector<ll> w_;
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
S_ = vector<ll>(S.begin(),S.end());
X_ = X;
M_ = M;
// sort the buses by leaving time (smallest to largest) then speed (largest to smallest)
// the arrival time for each bus is the prefix maximum of this array
for(int i=0;i<N;++i){
if (W[i] > X){
t.push_back(T[i]);
w.push_back(W[i]);
}
}
w_ = vector<ll>(w.begin(),w.end());
n = t.size();
// output w and t
for(int i=0;i<n;++i){
arrival[0][i] = t[i];
}
for(int j=1;j<M;++j){
//cout << "Foo" << endl;
vector<int> buses(n);
for(int i=0;i<n;++i) buses[i] = i;
// output buses
std::sort(buses.begin(), buses.end(), [&](int a, int b)->bool{
//cout << a << " " << b << endl;
if (arrival[j-1][a] < arrival[j-1][b]) return 1;
if (arrival[j-1][a] > arrival[j-1][b]) return 0;
if (w[a] < w[b]) return 1;
return 0;
});
//cout << "Foo" << endl;
sortOrders.push_back(buses);
ll pmax = 0;
for (auto& bus:buses){
arrival[j][bus] = max(pmax, arrival[j-1][bus]+w[bus]*(S[j]-S[j-1]));
pmax = max(pmax, arrival[j][bus]);
}
}
// output the arrival array
return;
}
long long arrival_time(long long Y)
{
ll tm = Y;
for(int j=1;j<M_;++j){
int bnd = upper_bound(sortOrders[j-1].begin(), sortOrders[j-1].end(),-1,[&](int a, int b)->bool{
if (tm <= arrival[j-1][b]) return 1;
return 0;
}) - sortOrders[j-1].begin();
if (bnd == 0) {
tm +=
X_*(S_[j]-S_[j-1]);
} else {
tm = max(tm+ X_*(S_[j]-S_[j-1]), arrival[j][sortOrders[j-1][bnd-1]]);
}
}
return tm;
}
/*
int main()
{
int L, N, X, M, Q;
assert(5 == scanf("%d %d %d %d %d", &L, &N, &X, &M, &Q));
std::vector<long long> T(N);
for (int i = 0; i < N; i++)
assert(1 == scanf("%lld", &T[i]));
std::vector<int> W(N);
for (int i = 0; i < N; i++)
assert(1 == scanf("%d", &W[i]));
std::vector<int> S(M);
for (int i = 0; i < M; i++)
assert(1 == scanf("%d", &S[i]));
std::vector<long long> Y(Q);
for (int i = 0; i < Q; i++)
assert(1 == scanf("%lld", &Y[i]));
fclose(stdin);
init(L, N, T, W, X, M, S);
std::vector<long long> res(Q);
for (int i = 0; i < Q; i++)
res[i] = arrival_time(Y[i]);
for (int i = 0; i < Q; i++)
printf("%lld\n", res[i]);
fclose(stdout);
return 0;
}
*/
