#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;
vector<int> seen;
// DP arrays per node: we'll return a triple of vectors
// dp0: u not chosen -> dp0[p] = min cost to have p participants in subtree
// dp1: u chosen but currently isolated (not participant yet) -> dp1[p] = min cost
// dp2: u chosen and already connected (participant) -> dp2[p] = min cost
struct Triple {
vector<ll> dp0, dp1, dp2;
};
Triple dfs(int u, int parent) {
// initialize
Triple cur;
cur.dp0 = {0}; // 0 participants, cost 0, u not chosen
cur.dp1 = {D[u]}; // 0 participants but u chosen and isolated (cost D[u])
cur.dp2 = {INF}; // impossible initially (no children yet to connect u)
int cursz = 0; // maximum participants count currently possible
for (int v : g[u]) {
if (v == parent) continue;
Triple ch = dfs(v, u);
// for child ch, bestChild[j] = min(ch.dp0[j], ch.dp1[j], ch.dp2[j])
int chMax = max({ (int)ch.dp0.size()-1, (int)ch.dp1.size()-1, (int)ch.dp2.size()-1 });
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));
}
int newMax = cursz + chMax;
vector<ll> n0(newMax+1, INF), n1(newMax+1, INF), n2(newMax+1, INF);
// iterate over current i and child j and combine
for (int i = 0; i <= cursz; ++i) {
// values from cur
ll cur0_i = (i < (int)cur.dp0.size()) ? cur.dp0[i] : INF;
ll cur1_i = (i < (int)cur.dp1.size()) ? cur.dp1[i] : INF;
ll cur2_i = (i < (int)cur.dp2.size()) ? cur.dp2[i] : INF;
for (int j = 0; j <= chMax; ++j) {
// child's three states
ll ch0_j = (j < (int)ch.dp0.size()) ? ch.dp0[j] : INF;
ll ch1_j = (j < (int)ch.dp1.size()) ? ch.dp1[j] : INF;
ll ch2_j = (j < (int)ch.dp2.size()) ? ch.dp2[j] : INF;
ll best_j = bestChild[j];
// 1) u not chosen (cur0) -> remains not chosen; child best
if (cur0_i < INF && best_j < INF) {
ll val = cur0_i + best_j;
n0[i + j] = min(n0[i + j], val);
}
// 2) u chosen but isolated so far (cur1)
if (cur1_i < INF) {
// if child not selected at root (ch0): u stays isolated
if (ch0_j < INF) {
n1[i + j] = min(n1[i + j], cur1_i + ch0_j);
}
// if child root selected but isolated (ch1): connecting u<->child
// => child root becomes participant (+1), u becomes connected (+1)
if (ch1_j < INF) {
// participants increase by 2
if (i + j + 2 <= newMax)
n2[i + j + 2] = min(n2[i + j + 2], cur1_i + ch1_j);
}
// if child root already connected (ch2): child counted, u becomes connected (+1)
if (ch2_j < INF) {
if (i + j + 1 <= newMax)
n2[i + j + 1] = min(n2[i + j + 1], cur1_i + ch2_j);
}
}
// 3) u chosen and already connected (cur2)
if (cur2_i < INF) {
// child not selected root
if (ch0_j < INF) {
n2[i + j] = min(n2[i + j], cur2_i + ch0_j);
}
// child root selected but isolated -> it becomes connected to u => +1 participant
if (ch1_j < INF) {
if (i + j + 1 <= newMax)
n2[i + j + 1] = min(n2[i + j + 1], cur2_i + ch1_j);
}
// child root already connected
if (ch2_j < INF) {
n2[i + j] = min(n2[i + j], cur2_i + ch2_j);
}
}
}
}
// move new arrays to cur
cur.dp0.swap(n0);
cur.dp1.swap(n1);
cur.dp2.swap(n2);
cursz = newMax;
}
// After processing children, arrays cur are ready.
// Note: cur.dp1 currently stores cost where u is chosen but isolated (u not counted).
// cur.dp2 stores cost where u is chosen and already counted.
// cur.dp0 stores cost where u not chosen.
// It's possible cur.dp2 has size 0 (if no possibility) - that's fine.
return cur;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
#if 0
// For local testing: redirect input files here if needed
freopen("input.txt","r",stdin);
#endif
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);
}
// find components (trees) and compute best vector per component
vector<char> vis(N, 0);
vector<vector<ll>> comps; // comps[t] = vector best[t] minimal cost to get t participants in this component
for (int i = 0; i < N; ++i) {
if (vis[i]) continue;
// BFS to collect component nodes (optional) and mark visited
vector<int> compNodes;
queue<int> q; q.push(i); vis[i]=1;
while (!q.empty()) {
int u = q.front(); q.pop();
compNodes.push_back(u);
for (int v: g[u]) if (!vis[v]) { vis[v]=1; q.push(v); }
}
// run dfs DP rooted at i (tree assumption)
Triple res = dfs(i, -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));
}
// Note: for root, dp1 means root chosen but isolated -> root not participant, that's already accounted.
comps.push_back(move(best));
}
// knapsack combine components: global[k] = min cost to have k participants across processed comps
vector<ll> global(1, 0); // global[0]=0
for (auto &best : comps) {
int sz1 = (int)global.size()-1;
int sz2 = (int)best.size()-1;
vector<ll> ng(sz1 + sz2 + 1, INF);
for (int a = 0; a <= sz1; ++a) if (global[a] < INF) {
for (int b = 0; b <= sz2; ++b) if (best[b] < INF) {
ng[a+b] = min(ng[a+b], global[a] + best[b]);
}
}
global.swap(ng);
}
// ensure global is nondecreasing in k (should be but numeric INF may cause gaps)
int maxK = (int)global.size()-1;
// For binary searching: global[k] is minimal cost for exactly k participants.
// cost should be nondecreasing; still we keep as is.
int Q; cin >> Q;
while (Q--) {
ll S; cin >> S;
// find largest k such that global[k] <= S
int lo = 0, hi = maxK, 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;
}
