#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (1LL<<60);
int N, M;
vector<ll> D;
vector<vector<int>> g;
vector<int> seen;
// DP returns triple of vectors dp0, dp1, dp2 for node u
// dp*_sz = number of possible good nodes in subtree (indices 0..sz)
struct Triple {
vector<ll> dp0, dp1, dp2;
};
Triple dfs(int u, int p) {
// initialize
Triple cur;
cur.dp0 = vector<ll>(1, 0); // if u not chosen: 0 cost, 0 good nodes
cur.dp1 = vector<ll>(1, D[u]); // if u chosen but not connected yet: cost D[u], 0 good nodes inside so far
cur.dp2 = vector<ll>(); // empty until it becomes possible
int size_cur = 0; // number of good nodes accounted so far in these arrays
for (int v : g[u]) if (v != p) {
Triple ch = dfs(v, u);
int s1 = size_cur;
int s2 = (int)max({ch.dp0.size(), ch.dp1.size(), ch.dp2.size()}) - 1;
int new_size = s1 + s2;
vector<ll> ndp0(new_size+1, INF), ndp1(new_size+1, INF), ndp2(new_size+1, INF);
// Helper: get cost arrays for child states (if index j out of range, cost = INF)
auto cost0 = [&](int j)->ll { return (j >= 0 && j < (int)ch.dp0.size()) ? ch.dp0[j] : INF; };
auto cost1 = [&](int j)->ll { return (j >= 0 && j < (int)ch.dp1.size()) ? ch.dp1[j] : INF; };
auto cost2 = [&](int j)->ll { return (j >= 0 && j < (int)ch.dp2.size()) ? ch.dp2[j] : INF; };
// Merge for dp0: parent not chosen -> child may be dp0 or dp2 only
for (int i = 0; i <= s1; ++i) if (i < (int)cur.dp0.size()) {
if (cur.dp0[i] >= INF) continue;
for (int j = 0; j <= s2; ++j) {
ll candi = min(cost0(j), cost2(j));
if (candi >= INF) continue;
ndp0[i+j] = min(ndp0[i+j], cur.dp0[i] + candi);
}
}
// Merge for dp2 (parent already connected): child can be dp0, dp2, or dp1 (dp1 resolves to +1 count)
if (!cur.dp2.empty()) {
for (int i = 0; i <= s1; ++i) if (i < (int)cur.dp2.size()) {
if (cur.dp2[i] >= INF) continue;
for (int j = 0; j <= s2; ++j) {
// child dp0 or dp2: counts add j
if (cost0(j) < INF) ndp2[i+j] = min(ndp2[i+j], cur.dp2[i] + cost0(j));
if (cost2(j) < INF) ndp2[i+j] = min(ndp2[i+j], cur.dp2[i] + cost2(j));
// child dp1: when parent is selected, child pending resolves: child contributes +1
if (cost1(j) < INF) ndp2[i + j + 1] = min(ndp2[i + j + 1], cur.dp2[i] + cost1(j));
}
}
}
// Merge for dp1 (parent chosen but not connected yet)
for (int i = 0; i <= s1; ++i) if (i < (int)cur.dp1.size()) {
if (cur.dp1[i] >= INF) continue;
for (int j = 0; j <= s2; ++j) {
// child dp0 or dp2: parent remains pending
if (cost0(j) < INF) ndp1[i+j] = min(ndp1[i+j], cur.dp1[i] + cost0(j));
if (cost2(j) < INF) ndp1[i+j] = min(ndp1[i+j], cur.dp1[i] + cost2(j));
// child dp1: connecting parent and child => parent becomes connected (+1), child becomes good (+1)
if (cost1(j) < INF) {
// added good nodes: child gives j+1, plus parent +1 -> total + (j+2)
ndp2[i + j + 2] = min(ndp2[i + j + 2], cur.dp1[i] + cost1(j));
}
}
}
// Also dp2 could be created from dp0 if dp0 was empty? No: dp0 cannot create dp2.
// Update cur with ndp*
// Trim trailing INF entries possibly to reduce sizes
auto trim = [&](vector<ll> &v) {
int last = (int)v.size() - 1;
while (last >= 0 && v[last] >= INF) --last;
v.resize(last+1);
if (v.empty()) v = vector<ll>(); // keep empty
};
cur.dp0 = ndp0; trim(cur.dp0);
cur.dp1 = ndp1; trim(cur.dp1);
cur.dp2 = ndp2; trim(cur.dp2);
size_cur = (int)max({cur.dp0.size(), cur.dp1.size(), cur.dp2.size()}) - 1;
if (size_cur < 0) size_cur = 0;
} // end foreach child
return cur;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> M;
D.assign(N, 0);
for (int i = 0; i < N; ++i) cin >> D[i];
g.assign(N, {});
for (int i = 0; i < M; ++i) {
int a,b; cin >> a >> b; --a; --b;
g[a].push_back(b);
g[b].push_back(a);
}
int Q; cin >> Q;
vector<ll> S(Q);
ll Smax = 0;
for (int i = 0; i < Q; ++i) { cin >> S[i]; Smax = max(Smax, S[i]); }
// find components and compute best_comp for each
vector<int> vis(N,0);
vector<vector<ll>> comps_best; // comps_best[k][c] = minimal cost to get c good nodes in that comp
for (int i = 0; i < N; ++i) if (!vis[i]) {
// BFS/DFS to mark component nodes
vector<int> stack = {i};
vis[i] = 1;
for (int idx = 0; idx < (int)stack.size(); ++idx) {
int u = stack[idx];
for (int v : g[u]) if (!vis[v]) { vis[v] = 1; stack.push_back(v); }
}
// run tree DP with root = i (component is a tree by problem statement)
Triple t = dfs(i, -1);
int maxc = 0;
if (!t.dp0.empty()) maxc = max(maxc, (int)t.dp0.size()-1);
if (!t.dp2.empty()) maxc = max(maxc, (int)t.dp2.size()-1);
vector<ll> best(maxc+1, INF);
// best[c] = min(dp0[c], dp2[c]) (dp1 invalid at root)
for (int c = 0; c <= maxc; ++c) {
ll val = INF;
if (c < (int)t.dp0.size()) val = min(val, t.dp0[c]);
if (c < (int)t.dp2.size()) val = min(val, t.dp2[c]);
best[c] = val;
}
// also possible to take c=0 with cost 0 even if not present
if (best.size() == 0) best = vector<ll>(1, 0);
else best[0] = min(best[0], 0LL);
comps_best.push_back(best);
}
// global knapsack by value: dp[v] = minimal cost to achieve total v good nodes across processed components
vector<ll> global(N+1, INF);
global[0] = 0;
for (auto &best : comps_best) {
int sz = (int)best.size()-1;
vector<ll> nxt(N+1, INF);
for (int have = 0; have <= N; ++have) {
if (global[have] >= INF) continue;
// take c from this comp
for (int c = 0; c <= sz; ++c) {
if (best[c] >= INF) continue;
if (have + c <= N) nxt[have + c] = min(nxt[have + c], global[have] + best[c]);
}
}
global.swap(nxt);
}
// For each query S[i], find max v with global[v] <= S[i]
for (int qi = 0; qi < Q; ++qi) {
ll s = S[qi];
int ans = 0;
for (int v = 0; v <= N; ++v) {
if (global[v] <= s) ans = v;
}
cout << ans << '\n';
}
return 0;
}
