#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;
}
tim mxtm(tim a,tim b){
if(a.exp >= b.exp) return a;
else return b;
}
int n;
struct lst{
vector<tim>v;
tim seg[4001];
void update(int ind,tim val){
ind += n;
seg[ind] = val;
ind /= 2;
while(ind){
seg[ind] = mxtm(seg[ind * 2],seg[ind * 2 + 1]);
ind /= 2;
}
}
tim query(int l,int r,int s,int e,int ind){
if(l > e || r < s) return {-1,-1,-1};
if(l >= s && r <= e) return seg[ind];
int md = (l + r) / 2;
return mxtm(query(l,md,s,e,ind * 2),query(md + 1,r,s,e,ind * 2 + 1));
}
void build(){
for(int i = 0;i < v.size();i++){
update(i,v[i]);
}
}
ll find(tim a){
ll x = lower_bound(v.begin(),v.end(),a) - v.begin();
x--;
// cout<<x<<' ';a.log();
// cout<<'\n';
if(x == -1){
return a.exp;
}
auto ans = query(1,n,1,x + 1,1);
return max(a.exp,ans.exp);
}
};
lst a[4001];
ll x;
ll m;
ll n1;
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 = exp2(ceil(log2(N)));
n1 = n;
for(int i = 0;i < N;i++){
a[0].v.push_back({T[i],ll(T[i] + ll((ll)(S[1] - S[0]) * (ll)W[i])),i});
}
sort(a[0].v.begin(),a[0].v.end());
a[0].build();
for(ll 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;
ll t = max(mx,x.exp);
ll id = x.i;
ll e = ll(t + (ll)((ll)(S[i + 1] - S[i]) * (ll)(W[id])));
a[i].v.push_back({t,e,id});
}
sort(a[i].v.begin(),a[i].v.end());
a[i].build();
}
// 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)(Y + (ll)((ll)(s[1] - s[0]) * (ll)x)),n1};
for(ll i = 1;i < m;i++){
// ans.log();
ll mx = max(a[i-1].find(ans),ans.exp);
if(i == m - 1) return mx;
ans = {mx,mx + (ll)(s[i + 1] - s[i]) * (ll)x,n1};
}
}
//
// 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;
// }
