#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (ll)9e18;
int N, M;
vector<ll> D;
vector<vector<int>> g;
// Triple DP (see discussion): dp0 = u not chosen, dp1 = u chosen but isolated, dp2 = u chosen and already connected
struct Triple {
vector<ll> dp0, dp1, dp2;
};
Triple dfs(int u, int p) {
Triple cur;
cur.dp0 = {0}; // 0 participants, cost 0, u not chosen
cur.dp1 = {D[u]}; // u chosen & isolated: currently contributes cost D[u], but not counted as participant
cur.dp2 = {INF}; // impossible yet (no child connected u)
int curMax = 0;
for (int v : g[u]) {
if (v == p) continue;
Triple ch = dfs(v, u);
int chMax = max({ (int)ch.dp0.size()-1, (int)ch.dp1.size()-1, (int)ch.dp2.size()-1 });
int newMax = curMax + chMax;
vector<ll> bestChild(chMax+1, INF);
for (int j = 0; j <= chMax; ++j) {
ll a = (j < (int)ch.dp0.size()) ? ch.dp0[j] : INF;
ll b = (j < (int)ch.dp1.size()) ? ch.dp1[j] : INF;
ll c = (j < (int)ch.dp2.size()) ? ch.dp2[j] : INF;
bestChild[j] = min(a, min(b, c));
}
vector<ll> n0(newMax+1, INF), n1(newMax+1, INF), n2(newMax+1, INF);
for (int i = 0; i <= curMax; ++i) {
ll cur0 = (i < (int)cur.dp0.size()) ? cur.dp0[i] : INF;
ll cur1 = (i < (int)cur.dp1.size()) ? cur.dp1[i] : INF;
ll cur2 = (i < (int)cur.dp2.size()) ? cur.dp2[i] : INF;
for (int j = 0; j <= chMax; ++j) {
ll ch0 = (j < (int)ch.dp0.size()) ? ch.dp0[j] : INF;
ll ch1 = (j < (int)ch.dp1.size()) ? ch.dp1[j] : INF;
ll ch2 = (j < (int)ch.dp2.size()) ? ch.dp2[j] : INF;
ll bestj = bestChild[j];
// u not chosen -> child best
if (cur0 < INF && bestj < INF) n0[i+j] = min(n0[i+j], cur0 + bestj);
// u chosen but isolated
if (cur1 < INF) {
if (ch0 < INF) n1[i+j] = min(n1[i+j], cur1 + ch0);
if (ch1 < INF && i + j + 2 <= newMax) n2[i+j+2] = min(n2[i+j+2], cur1 + ch1);
if (ch2 < INF && i + j + 1 <= newMax) n2[i+j+1] = min(n2[i+j+1], cur1 + ch2);
}
// u chosen and already connected
if (cur2 < INF) {
if (ch0 < INF) n2[i+j] = min(n2[i+j], cur2 + ch0);
if (ch1 < INF && i + j + 1 <= newMax) n2[i+j+1] = min(n2[i+j+1], cur2 + ch1);
if (ch2 < INF) n2[i+j] = min(n2[i+j], cur2 + ch2);
}
}
}
cur.dp0.swap(n0);
cur.dp1.swap(n1);
cur.dp2.swap(n2);
curMax = newMax;
}
// after children, cur.dp1 means u chosen but isolated (u not participant)
// cur.dp2 means u chosen & participant
// ensure dp sizes / base cases ok
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);
}
vector<char> vis(N, 0);
vector<vector<ll>> comps; // comps[t] = min cost to get t participants in this component
for (int i = 0; i < N; ++i) if (!vis[i]) {
// BFS to mark component nodes
vector<int> nodes;
queue<int> q; q.push(i); vis[i]=1;
while (!q.empty()) {
int u = q.front(); q.pop();
nodes.push_back(u);
for (int v : g[u]) if (!vis[v]) { vis[v]=1; q.push(v); }
}
// run dfs from nodes[0] as root
Triple res = dfs(nodes[0], -1);
int mx = max({ (int)res.dp0.size()-1, (int)res.dp1.size()-1, (int)res.dp2.size()-1 });
vector<ll> best(mx+1, INF);
for (int t = 0; t <= mx; ++t) {
ll a = (t < (int)res.dp0.size()) ? res.dp0[t] : INF;
ll b = (t < (int)res.dp1.size()) ? res.dp1[t] : INF;
ll c = (t < (int)res.dp2.size()) ? res.dp2[t] : INF;
best[t] = min(a, min(b, c));
}
comps.push_back(move(best));
}
// knapsack combine components
vector<ll> global(1, 0); // global[0] = 0
for (auto &best : comps) {
int s1 = (int)global.size()-1;
int s2 = (int)best.size()-1;
vector<ll> ng(s1 + s2 + 1, INF);
for (int a = 0; a <= s1; ++a) if (global[a] < INF) {
for (int b = 0; b <= s2; ++b) if (best[b] < INF) {
ng[a+b] = min(ng[a+b], global[a] + best[b]);
}
}
global.swap(ng);
}
// answer queries
int Q; cin >> Q;
while (Q--) {
ll S; cin >> S;
int lo = 0, hi = (int)global.size()-1, ans = 0;
while (lo <= hi) {
int mid = (lo + hi) >> 1;
if (global[mid] <= S) { ans = mid; lo = mid + 1; }
else hi = mid - 1;
}
cout << ans << '\n';
}
return 0;
}
