#include <bits/stdc++.h>
using namespace std ;
#include "overtaking.h"
#define int long long
int st[1003][1003] ;
int pos[1003][1003] ;
vector <tuple<int,int,int>> vvv[1003] ;
struct SEGT {
int seg[4003] ;
void build(){for (int i = 0 ; i < 4003 ; i ++) seg[i]=-1 ;}
void upd(int id,int l,int r,int x,int v){
if (l==r&&l==x) seg[id]=v ;
else if (l>x||r<x) ;
else {
int md=(l+r)/2 ;
upd(id*2,l,md,x,v) ;
upd(id*2+1,md+1,r,x,v) ;
seg[id]=max(seg[id*2],seg[id*2+1]) ;
}
}
int qq(int id,int l,int r,int ql,int qr){
if (ql<=l&&r<=qr) return seg[id] ;
else if (l>qr||r<ql) return -1 ;
else {
int md=(l+r)/2 ;
return max(qq(id*2,l,md,ql,qr),qq(id*2+1,md+1,r,ql,qr)) ;
}
}
} sgt[1003] ;
struct SEGT2 {
int seg[1000003] ;
int lzt[1000003] ;
int lc[1000003] ;
int rc[1000003] ;
int cnt=2 ;
void open(int id){
if (lc[id]!=0) ;
else {
lc[id]=cnt++ ;
rc[id]=cnt++ ;
seg[lc[id]]=-1 ;
seg[rc[id]]=-1 ;
lzt[lc[id]]=-1 ;
lzt[rc[id]]=-1 ;
}
}
void build(){for (int i = 0 ; i < 1000003 ; i ++) seg[i]=lzt[i]=-1,lc[i]=rc[i]=0 ;}
void pd(int id){
lzt[lc[id]]=max(lzt[lc[id]],lzt[id]) ;
lzt[rc[id]]=max(lzt[rc[id]],lzt[id]) ;
seg[lc[id]]=max(seg[lc[id]],lzt[id]) ;
seg[rc[id]]=max(seg[rc[id]],lzt[id]) ;
lzt[id]=-1 ;
}
void upd(int id,int l,int r,int ql,int qr,int x){
if (ql<=l&&r<=qr) seg[id]=max(seg[id],x),lzt[id]=max(lzt[id],x) ;
else if (l>qr||r<ql) ;
else {
open(id) ;
pd(id) ;
int md=(l+r)/2 ;
upd(lc[id],l,md,ql,qr,x) ;
upd(rc[id],md+1,r,ql,qr,x) ;
}
}
int qq(int id,int l,int r,int x){
if (l==r&&l==x) return (seg[id]==-1?x:seg[id]) ;
else if (l>x||r<x) return -1 ;
else {
open(id) ;
pd(id) ;
int md=(l+r)/2 ;
return max(qq(lc[id],l,md,x),qq(rc[id],md+1,r,x)) ;
}
}
} sgt2 ;
int ADD ;
void init(signed L, signed N, std::vector<long long> TT, std::vector<signed> WW, signed X, signed M, std::vector<signed> S){
ADD=X*S[M-1] ;
int i,j ;
for (i = 0 ; i < N ; i ++) WW[i]-=X ;
vector <int> W,T ;
for (i = 0 ; i < N ; i ++) if (WW[i]>0) W.push_back(WW[i]),T.push_back(TT[i]) ;
N=(int)W.size() ;
vector <pair<int,int>> vv ;
for (i = 0 ; i < N ; i ++) vv.push_back({W[i],i}) ;
sort(vv.begin(),vv.end(),greater<pair<int,int>>()) ;
for (i = 0 ; i < N ; i ++) st[0][i]=T[i] ;
for (i = 0 ; i < M-1 ; i ++){
sgt[i].build() ;
for (j = 0 ; j < N ; j ++) vvv[i].push_back({st[i][j],W[j],j}) ;
sort(vvv[i].begin(),vvv[i].end()) ;
for (j = 0 ; j < N ; j ++) pos[i][get<2>(vvv[i][j])]=j+1 ;
for (auto [xx,x] : vv){
st[i+1][x]=st[i][x]+(S[i+1]-S[i])*W[x] ;
st[i+1][x]=max(st[i+1][x],sgt[i].qq(1,1,N,1,pos[i][x])) ;
sgt[i].upd(1,1,N,pos[i][x],st[i+1][x]) ;
}
// for (j = 0 ; j < N ; j ++) cout << st[i+1][j] << " " ; cout << endl ;
}
// for (j = 0 ; j < N ; j ++) pre[M-1][j]=st[M-1][j] ;
sgt2.build() ;
for (j = 0 ; j < N ; j ++) sgt2.upd(1,0,LLONG_MAX/4,st[M-2][j]+1,st[M-1][j],st[M-1][j]) ;
for (i = M-3 ; i >= 0 ; i --){
vector <int> pre(N,0) ;
for (j = 0 ; j < N ; j ++){
pre[j]=sgt2.qq(1,0,LLONG_MAX/4,st[i+1][j]) ;
}
for (j = 0 ; j < N ; j ++){
sgt2.upd(1,0,LLONG_MAX/4,st[i][j]+1,st[i+1][j],pre[j]) ;
}
}
return;
}
long long arrival_time(long long Y){
return sgt2.qq(1,0,LLONG_MAX/4,Y)+ADD ;
}
#undef int
// #define test
#ifdef test
#include <cassert>
#include <cstdio>
#include <vector>
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;
}
#endif
