#include <bits/stdc++.h>
#define rep(a,b,c) for(int a=b; a<c; a++)
#define repr(a,b,c) for(int a=b-1; a>c-1; a--)
#define repa(a,b) for(auto a:b)
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ll long long
#define pb push_back
using namespace std;
struct buses{
ll m, b, i;
ll eval(ll x){
return m*x+b;
}
bool operator<(buses B){
if(b==B.b) return m<B.m;
return b<B.b;
}
};
ll n, m, h, x, ti[1005][1005], tf[1005][1005], s[1005];
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S){
n=N, h=L, x=X, m=M;
vector<buses> bus;
rep(i,0,n) bus.pb({W[i],T[i],i});
rep(i,0,m) s[i]=S[i];
ll l=0, f[n];
rep(j,0,m){
sort(bus.begin(),bus.end());
rep(i,0,n){
bus[i].b=bus[i].eval(S[j]-l);
if(i) bus[i].b=max(bus[i-1].b,bus[i].b);
f[i]=bus[i].b;
}
rep(i,0,n){
ti[j][i]=bus[i].b;
tf[j][i]=bus[i].i;
}
l=S[j];
}
rep(j,0,m){
rep(i,0,n){
tf[j][i]=f[bus[i].i];
if(i) tf[j][i]=max(tf[j][i-1],tf[j][i]);
}
}
}
long long arrival_time(long long Y){
int l=0, r=m-1, mid, L, R, MID;
ll dis;
while(l<=r){
mid=(l+r)>>1;
dis=(x*s[mid])+Y;
L=0, R=n-1;
while(L<=R){
MID=(L+R)>>1;
if(ti[mid][MID]>=dis) R=MID-1;
else L=MID+1;
}
if(L<n) dis=max(dis,ti[mid][L]);
dis+=(h-s[mid])*x;
if(L==n || tf[mid][R]<=dis) r=mid-1;
else l=mid+1;
}
dis=(x*s[l])+Y;
L=0, R=n-1;
while(L<=R){
MID=(L+R)>>1;
if(ti[l][MID]>=dis) R=MID-1;
else L=MID+1;
}
if(L) dis=max(dis,ti[l][L]);
dis+=(h-s[l])*x;
return dis;
}
