// dzumbus_fixed.cpp
#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 not yet satisfied by child (pending): dp1[k] = min cost, k good nodes in subtree (not counting u)
vector<ll> dp2; // u chosen and already satisfied by some child (so u is counted): dp2[k] = min cost, k good nodes in subtree (including u)
};
Triple dfs(int u, int p){
Triple cur;
cur.dp0 = {0}; // 0 good nodes, cost 0
cur.dp1 = {D[u]}; // 0 good nodes yet, but u chosen cost D[u]
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 maxc_for_any = max({c0, c1, c2, 0});
int new_max = max({s0, s1, s2, 0}) + maxc_for_any + 2; // +2 to be safe for transitions that add +2
vector<ll> ndp0(new_max+1, INF), ndp1(new_max+1, INF), ndp2(new_max+1, INF);
auto cost = [&](const vector<ll> &vec, int j)->ll{
if (j < 0) return INF;
if (j >= (int)vec.size()) return INF;
return vec[j];
};
// Merge for dp0: parent not chosen -> child can be in dp0 or dp2
for (int i = 0; i <= s0; ++i){
ll base = cost(cur.dp0, i);
if (base >= INF) continue;
for (int j = 0; j <= max(c0, c2); ++j){
ll cst = min(cost(ch.dp0, j), cost(ch.dp2, j));
if (cst >= INF) continue;
ndp0[i + j] = min(ndp0[i + j], base + cst);
}
}
// Merge for dp1: parent chosen but pending -> child dp0 or dp2 keeps parent pending
// child dp1 connects parent and child -> goes to dp2 and adds +2 (child becomes good +1, parent becomes good +1)
for (int i = 0; i <= s1; ++i){
ll base = cost(cur.dp1, i);
if (base >= INF) continue;
for (int j = 0; j <= max({c0,c1,c2}); ++j){
// child dp0
if (cost(ch.dp0, j) < INF) ndp1[i + j] = min(ndp1[i + j], base + cost(ch.dp0, j));
// child dp2
if (cost(ch.dp2, j) < INF) ndp1[i + j] = min(ndp1[i + j], base + cost(ch.dp2, j));
// child dp1 => resolves both child and parent -> move to dp2
if (cost(ch.dp1, j) < INF){
ndp2[i + j + 2] = min(ndp2[i + j + 2], base + cost(ch.dp1, j));
}
}
}
// Merge for dp2: parent already satisfied -> child dp0 or dp2 add j goods; child dp1 will be satisfied by parent and add +1
if (!cur.dp2.empty()){
for (int i = 0; i <= s2; ++i){
ll base = cost(cur.dp2, i);
if (base >= INF) continue;
for (int j = 0; j <= max({c0,c1,c2}); ++j){
if (cost(ch.dp0, j) < INF) ndp2[i + j] = min(ndp2[i + j], base + cost(ch.dp0, j));
if (cost(ch.dp2, j) < INF) ndp2[i + j] = min(ndp2[i + j], base + cost(ch.dp2, j));
if (cost(ch.dp1, j) < INF) ndp2[i + j + 1] = min(ndp2[i + j + 1], base + cost(ch.dp1, j));
}
}
}
// Trim trailing INF and assign back
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 legitimately be empty
cur.dp0.swap(ndp0);
cur.dp1.swap(ndp1);
cur.dp2.swap(ndp2);
}
return cur;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (!(cin >> N >> M)) return 0;
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);
vector<vector<ll>> comps;
for (int i = 0; i < N; ++i) if (!vis[i]){
// collect 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 dfs 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;
}
// ensure best[0]=0
if (best.size() == 0) best = {0};
else best[0] = min(best[0], 0LL);
comps.push_back(best);
}
// global knapsack by value
vector<ll> dp(N+1, INF);
dp[0] = 0;
for (auto &best : comps){
vector<ll> ndp(N+1, INF);
int sz = (int)best.size() - 1;
for (int have = 0; have <= N; ++have){
if (dp[have] >= INF) continue;
for (int c = 0; c <= sz; ++c){
if (best[c] >= INF) continue;
if (have + c <= N) ndp[have + c] = min(ndp[have + c], dp[have] + best[c]);
}
}
dp.swap(ndp);
}
for (int qi = 0; qi < Q; ++qi){
ll s = S[qi];
int ans = 0;
for (int v = 0; v <= N; ++v) if (dp[v] <= s) ans = v;
cout << ans << "\n";
}
return 0;
}
