#include <bits/stdc++.h>
typedef long long ll;
#define F first
#define S second
const ll mod = 1e9 + 7;
const ll mxN = 1e5 + 2;
using namespace std;
struct tim{
ll time,exp,i;
void log(){
cout<<"{ "<<time<<" , "<<exp<<" , "<<i<<" } ";
}
};
bool operator>(tim c, tim b){
return c.time > b.time;
}
bool operator<(tim c, tim b){
return c.time < b.time;
}
int n;
struct lst{
vector<tim>v;
};
lst a[4001];
ll x;
int m;
vector<int>s;
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
m = M;
x = ll(X);
s = S;
n = N;
for(int i = 0;i < N;i++){
a[0].v.push_back({T[i],T[i] + (ll)(S[1] - S[0]) * (ll)W[i],i});
}
sort(a[0].v.begin(),a[0].v.end());
for(int i = 1;i < M - 1;i++){
ll mx = 0;
ll prev = -1;
queue<ll>q;
for(auto x : a[i - 1].v){
if(x.time != prev){
while(q.size()){
mx = max(mx,q.front());
q.pop();
}
}
q.push(x.exp);
prev = x.time;
int t = max(mx,x.exp);
int id = x.i;
int e = t + (S[i + 1] - S[i]) * W[id];
a[i].v.push_back({t,e,id});
}
sort(a[i].v.begin(),a[i].v.end());
}
// for(int i = 0;i < M - 1;i++){
// for(auto x : a[i].v){
// x.log();
// }
// cout<<'\n';
// }
}
long long arrival_time(long long Y)
{
tim ans = {Y,(ll)(s[1] - s[0]) * (ll)x,n};
for(int i = 1;i < m;i++){
// ans.log();
ll mx = ans.exp;
for(auto x : a[i - 1].v){
if(x.time < ans.time) mx = max(x.exp,mx);
else break;
}
if(i == m - 1) return mx;
ans = {mx,mx + ll(s[i + 1] - s[i]) * (ll)x,n};
}
}
// 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;
// }
