#ifndef LOCAL
#include "overtaking.h"
#endif // LOCAL
#ifdef LOCAL
#include <vector>
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S);
long long arrival_time(long long Y);
#endif // LOCAL
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct bus {
int start_time;
int speed;
};
vector<bus> glob_busses;
vector<int> stations;
int X_init;
#undef int
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S) {
#define int long long
// scad X (viteza autobuzului de query) din fiecare viteza de autobuz (W)
for(int i = 0; i < N; ++i) {
W[i] -= X;
}
X_init = X;
// initialize busses
for(int i = 0; i < N; ++i) {
bus b;
b.start_time = T[i];
b.speed = W[i];
if(W[i] <= 0) continue; // acest autobuz nu afecteaza autobuzul meu!
glob_busses.push_back(b);
}
// initialize stations
for(int i = 0; i < M; ++i) {
stations.push_back(S[i]);
}
}
long long arrival_time_brut(long long Y) {
auto busses = glob_busses;
busses.push_back({Y, 0}); // autobuzul meu incepe la timpul Y si are viteza 0
sort(busses.begin(), busses.end(), [](bus a, bus b) {
if(a.start_time != b.start_time)
return a.start_time < b.start_time;
return a.speed < b.speed;
});
for(int i = 0; i + 1 < stations.size(); i++) {
int distance = stations[i + 1] - stations[i];
int max_prefix = -1e9;
vector<bus> new_busses;
for(auto b : busses) {
max_prefix = max(max_prefix, b.start_time + distance * b.speed);
new_busses.push_back({max_prefix, b.speed});
}
busses = new_busses;
sort(busses.begin(), busses.end(), [](bus a, bus b) {
if(a.start_time != b.start_time)
return a.start_time < b.start_time;
return a.speed < b.speed;
});
}
for(auto b : busses) {
if(b.speed == 0) return b.start_time;
}
assert(false); // nu se poate ajunge aici
}
long long arrival_time(long long Y) {
long long answer = arrival_time_brut(Y);
return answer + 1LL * (stations.back() - stations[0]) * X_init;
}
#ifdef LOCAL
#undef int
// Grader
#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 // LOCAL
