#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;
struct Triple {
vector<ll> dp0; // u NOT chosen: dp0[k] = min cost to have k good nodes in subtree
vector<ll> dp1; // u chosen but pending (no neighbor chosen yet inside subtree): dp1[k] -> k good nodes in subtree (excluding u)
vector<ll> dp2; // u chosen and connected (u counted): dp2[k] -> k good nodes in subtree (including u)
};
// DFS returns Triple for subtree rooted at u (parent = p)
Triple dfs(int u, int p) {
Triple cur;
cur.dp0 = {0}; // no good nodes, cost 0
cur.dp1 = {D[u]}; // choose u, but pending (not yet connected), cost D[u], contributes 0 good nodes so far
cur.dp2 = {}; // impossible initially
for (int v : g[u]) if (v != p) {
Triple ch = dfs(v, u);
int s0 = (int)cur.dp0.size() - 1;
int s1 = (int)cur.dp1.size() - 1;
int s2 = (int)cur.dp2.size() - 1;
int c0 = (int)ch.dp0.size() - 1;
int c1 = (int)ch.dp1.size() - 1;
int c2 = (int)ch.dp2.size() - 1;
int maxChild = max({c0,c1,c2,0});
int newMax = max({s0,s1,s2,0}) + maxChild + 2; // +2 for transitions that add +2
vector<ll> ndp0(newMax+1, INF), ndp1(newMax+1, INF), ndp2(newMax+1, INF);
auto get = [&](const vector<ll>& v, int idx)->ll{
if (idx < 0 || idx >= (int)v.size()) return INF;
return v[idx];
};
// parent NOT chosen: child can be not chosen (dp0) or child chosen+connected (dp2).
for (int i = 0; i <= s0; ++i) {
ll base = get(cur.dp0, i);
if (base >= INF) continue;
for (int j = 0; j <= max(c0, c2); ++j) {
ll chCost = min(get(ch.dp0, j), get(ch.dp2, j));
if (chCost >= INF) continue;
ndp0[i + j] = min(ndp0[i + j], base + chCost);
}
}
// parent chosen but pending (dp1)
// - child dp0 or dp2: parent remains pending
// - child dp1: if both parent and child pending -> they connect => both counted: +2
for (int i = 0; i <= s1; ++i) {
ll base = get(cur.dp1, i);
if (base >= INF) continue;
for (int j = 0; j <= max({c0,c1,c2}); ++j) {
if (get(ch.dp0, j) < INF) ndp1[i + j] = min(ndp1[i + j], base + get(ch.dp0, j));
if (get(ch.dp2, j) < INF) ndp1[i + j] = min(ndp1[i + j], base + get(ch.dp2, j));
if (get(ch.dp1, j) < INF) {
// child becomes good (+1) and parent becomes good (+1) => +2
ndp2[i + j + 2] = min(ndp2[i + j + 2], base + get(ch.dp1, j));
}
}
}
// parent already connected (dp2)
// - child dp0 or dp2: add j goods
// - child dp1: child resolves by parent => child counted (+1)
if (!cur.dp2.empty()) {
for (int i = 0; i <= s2; ++i) {
ll base = get(cur.dp2, i);
if (base >= INF) continue;
for (int j = 0; j <= max({c0,c1,c2}); ++j) {
if (get(ch.dp0, j) < INF) ndp2[i + j] = min(ndp2[i + j], base + get(ch.dp0, j));
if (get(ch.dp2, j) < INF) ndp2[i + j] = min(ndp2[i + j], base + get(ch.dp2, j));
if (get(ch.dp1, j) < INF) ndp2[i + j + 1] = min(ndp2[i + j + 1], base + get(ch.dp1, j));
}
}
}
// trim trailing INF
auto trim = [&](vector<ll>& v){
int last = (int)v.size() - 1;
while (last >= 0 && v[last] >= INF) --last;
v.resize(last + 1);
};
trim(ndp0); trim(ndp1); trim(ndp2);
if (ndp0.empty()) ndp0 = {INF};
if (ndp1.empty()) ndp1 = {INF};
// ndp2 may be empty legitimately
cur.dp0.swap(ndp0);
cur.dp1.swap(ndp1);
cur.dp2.swap(ndp2);
}
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);
for (int i = 0; i < Q; ++i) cin >> S[i];
vector<int> vis(N,0);
// comps_best[c] = minimal cost to get c good nodes in that component
vector<vector<ll>> comps_best;
for (int i = 0; i < N; ++i) if (!vis[i]) {
// collect component nodes
vector<int> stk = {i};
vis[i] = 1;
for (int idx = 0; idx < (int)stk.size(); ++idx) {
int u = stk[idx];
for (int v : g[u]) if (!vis[v]) { vis[v] = 1; stk.push_back(v); }
}
// run tree DP with root i
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);
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;
}
if (best.empty()) best = {0};
else best[0] = min(best[0], 0LL);
comps_best.push_back(best);
}
// global knapsack by value (number of good nodes)
vector<ll> global(N+1, INF);
global[0] = 0;
for (auto &best : comps_best) {
vector<ll> nxt(N+1, INF);
int sz = (int)best.size() - 1;
for (int have = 0; have <= N; ++have) {
if (global[have] >= INF) continue;
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);
}
// answer queries: for each S[i], output 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;
}
