#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std ;
#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] ;
vector <int> vvvvv ;
struct SEGT2 {
int seg[12000003] ;
int lzt[12000003] ;
void build(){for (int i = 0 ; i < 12000003 ; i ++) seg[i]=lzt[i]=-1 ;}
void pd(int id){
lzt[id*2]=max(lzt[id*2],lzt[id]) ;
lzt[id*2+1]=max(lzt[id*2+1],lzt[id]) ;
seg[id*2]=max(seg[id*2],lzt[id]) ;
seg[id*2+1]=max(seg[id*2+1],lzt[id]) ;
lzt[id]=-1ll ;
}
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 {
pd(id) ;
int md=(l+r)/2ll ;
upd(id*2,l,md,ql,qr,x) ;
upd(id*2+1,md+1ll,r,ql,qr,x) ;
}
}
int qq(int id,int l,int r,int x){
if (l==r&&l==x) return seg[id] ;
else if (l>x||r<x) return -1ll ;
else {
pd(id) ;
int md=(l+r)/2ll ;
return max(qq(id*2,l,md,x),qq(id*2+1,md+1ll,r,x)) ;
}
}
} sgt2 ;
int ADD ;
int L,N,X,M ;
void init(signed LL, signed NN, std::vector<long long> TT, std::vector<signed> WW, signed XX, signed MM, std::vector<signed> SS){
L=LL,N=NN,X=XX,M=MM ;
vector <int> S ;
for (auto x : SS) S.push_back(x) ;
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] ;
set <int> sttt ;
for (i = 0 ; i < M ; i ++) for (j = 0 ; j < N ; j ++) sttt.insert(st[i][j]),sttt.insert(st[i][j]+1),sttt.insert(st[i][j]-1) ;
map <int,int> mp ;
sttt.insert(-1) ;
i=0 ;
for (auto x : sttt) vvvvv.push_back(x),mp[x]=i++ ;
sgt2.build() ;
for (j = 0 ; j < N ; j ++) sgt2.upd(1,1,N*M*3,mp[st[M-2][j]+1],mp[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]=max(st[i+1][j],sgt2.qq(1,1,N*M*3,mp[st[i+1][j]])) ;
}
for (j = 0 ; j < N ; j ++){
sgt2.upd(1,1,N*M*3,mp[st[i][j]+1ll],mp[st[i+1][j]],pre[j]) ;
}
}
return;
}
long long arrival_time(long long Y){
return max(Y,sgt2.qq(1,1,N*M*3,lower_bound(vvvvv.begin(),vvvvv.end(),Y)-vvvvv.begin()))+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
/*
80000001 1 151251000 400 1
10000
151251252
0 563193 647572 715146 1130358 1138744 1557704 2110181 2300143 2420378 2557533 2614949 2657752 2838017 2861875 3146425 3202178 3240281 3248583 3280296 3310987 3401711 3683587 3943976 4135364 4214616 4277932 4503844 4764651 4796196 4821682 4867943 5042804 5486093 5792971 5795583 6143476 6564607 6876611 7190358 7590197 7621017 7623086 7886486 8051826 8104714 8971032 9055213 9550916 9774456 9871401 9903835 10116711 10274129 10795027 10805966 10927130 11127077 11316017 11391327 11562771 11787183 12292303 12543137 12587850 12674166 12867715 12877831 12905634 13391318 13483162 13577718 13678296 13696800 14095079 14122968 14146693 14248142 14262779 14921652 15041817 15182026 15464980 15538168 15917012 16338255 16343707 16503216 17117655 17151299 17248992 17676733 18320706 18347214 18505019 18745561 18866903 18987311 19304464 19430033 19663038 20282373 20323263 20596457 20940401 20991589 21088060 21140792 21257789 21506479 21631203 21633838 22077263 22289496 22694019 22758752 22912412 23069477 23156657 23295745 23298689 23640358 23718955 23806039 23815116 24216166 24323616 24395425 24406621 24661006 25216249 25689640 25701947 25818006 26627637 26781544 27514298 27892924 27950425 28204583 28250005 28455485 28483527 28514522 28923815 29061789 29172712 29415866 29770970 30198839 30269799 30415956 30628918 30950968 31074818 31088499 31092218 31098200 31202111 31466951 31691948 32328423 32860792 33119641 33262778 33366658 33487551 33541248 33659225 33766939 33952646 34049845 34053925 34113084 34318139 34441516 34528923 34775334 34816796 35143221 35425720 35680603 35988808 36002663 36096851 36654826 36768966 36830655 37411465 37460469 38166067 38389846 38518922 38866873 39024187 39779789 39830946 40707800 41046652 41060205 41357376 41375906 41390817 41548860 41570730 41855037 42001285 42453863 42743666 43576100 43639946 44018156 44136646 44213287 44389494 44893574 45260067 45775096 45829841 46197877 46296942 47080198 47484485 47502903 47789193 47994195 48124198 48276963 48295434 48332712 48347707 48460314 48571568 48634722 48857190 48889549 49148381 49188493 49203984 49937088 49959424 50050074 50076270 50116161 50319905 51003101 51004740 51345748 51439126 51640643 51749777 51779273 52342787 52424648 52493142 52583952 52728307 52741199 52818947 52971956 53021715 53668770 53935929 54052685 54079233 54245892 54346729 54582395 54858332 55119782 55317234 55331836 55656199 55937660 56105210 56232660 56338636 56763046 56776371 56856102 56869379 57122925 57398726 57803501 58214775 58303911 58900892 59214615 59686283 59707319 59812468 59830098 60105633 60217222 60589032 60852965 60915753 61027296 61277254 61342296 61866449 61876006 61928959 62172925 62188420 62331131 62350686 62396998 62586748 62633939 62691340 63132595 63417767 63455392 64096957 64393123 64398036 64700492 64754461 64988433 65211421 65311495 65353529 65600395 65604213 65619914 65740332 65768556 65826468 66051437 66833654 66849211 67221750 67386332 67679131 68096263 68217393 68325877 68473415 68474061 68481086 68652549 68704936 68730462 68912914 68952667 69010187 69095649 69174771 69323640 69490928 69563184 69687145 69892052 70110331 70208141 70272817 70329388 70472969 70513393 70565343 70624019 70639293 71183140 71518521 71878069 72597463 73038207 73184117 73494665 73626625 74021524 74837504 74856359 74886798 75147207 75230428 75455691 75979935 76196085 76405793 76712511 76965868 77096671 77276000 77876172 77990742 78007883 78026270 78511425 78638245 78682116 78912604 79020025 79115747 79354534 79368699 79416673 79656284 80000001
15591195568
*/
