#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
const long long INF = 1e18;
int N, M;
int D[MAXN];
vector<int> graph[MAXN];
bool visited[MAXN];
vector<int> components[MAXN];
int comp_index;
long long dp[MAXN];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N >> M;
for (int i = 1; i <= N; i++) {
cin >> D[i];
}
for (int i = 0; i < M; i++) {
int a, b;
cin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
}
memset(visited, false, sizeof(visited));
comp_index = 0;
for (int i = 1; i <= N; i++) {
if (!visited[i] && !graph[i].empty()) {
queue<int> q;
q.push(i);
visited[i] = true;
components[comp_index].push_back(i);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : graph[u]) {
if (!visited[v]) {
visited[v] = true;
components[comp_index].push_back(v);
q.push(v);
}
}
}
comp_index++;
}
}
for (int s = 0; s <= N; s++) {
dp[s] = INF;
}
dp[0] = 0;
for (int i = 0; i < comp_index; i++) {
vector<int> comp = components[i];
int L = comp.size();
if (L < 2) continue;
map<int, int> global_to_local;
vector<int> cost_local(L);
for (int j = 0; j < L; j++) {
int global_node = comp[j];
global_to_local[global_node] = j;
cost_local[j] = D[global_node];
}
vector<vector<int>> adj_local(L);
for (int j = 0; j < L; j++) {
int global_node = comp[j];
for (int neighbor : graph[global_node]) {
if (global_to_local.find(neighbor) != global_to_local.end()) {
int k = global_to_local[neighbor];
adj_local[j].push_back(k);
}
}
}
vector<long long> comp_cost(L+1, INF);
if (L <= 20) {
for (int mask = 0; mask < (1 << L); mask++) {
int count = 0;
long long cost = 0;
for (int j = 0; j < L; j++) {
if (mask & (1 << j)) {
count++;
cost += cost_local[j];
}
}
bool valid = true;
for (int j = 0; j < L; j++) {
if (mask & (1 << j)) {
bool has_neighbor = false;
for (int k : adj_local[j]) {
if (mask & (1 << k)) {
has_neighbor = true;
break;
}
}
if (!has_neighbor) {
valid = false;
break;
}
}
}
if (valid) {
if (cost < comp_cost[count]) {
comp_cost[count] = cost;
}
}
}
} else {
vector<pair<int, int>> edges;
for (int j = 0; j < L; j++) {
for (int k : adj_local[j]) {
if (j < k) {
edges.push_back({j, k});
}
}
}
sort(edges.begin(), edges.end(), [&](const pair<int, int> &e1, const pair<int, int> &e2) {
long long cost1 = cost_local[e1.first] + cost_local[e1.second];
long long cost2 = cost_local[e2.first] + cost_local[e2.second];
return cost1 < cost2;
});
int K = min(50, (int)edges.size());
for (int e_idx = 0; e_idx < K; e_idx++) {
int u = edges[e_idx].first;
int v = edges[e_idx].second;
vector<bool> inS(L, false);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
inS[u] = true;
inS[v] = true;
long long cost_total = cost_local[u] + cost_local[v];
if (cost_total < comp_cost[2]) {
comp_cost[2] = cost_total;
}
for (int neighbor : adj_local[u]) {
if (!inS[neighbor]) {
pq.push({cost_local[neighbor], neighbor});
}
}
for (int neighbor : adj_local[v]) {
if (!inS[neighbor]) {
pq.push({cost_local[neighbor], neighbor});
}
}
for (int s = 3; s <= L; s++) {
while (!pq.empty() && inS[pq.top().second]) {
pq.pop();
}
if (pq.empty()) break;
int c = pq.top().first;
int node = pq.top().second;
pq.pop();
inS[node] = true;
cost_total += c;
if (cost_total < comp_cost[s]) {
comp_cost[s] = cost_total;
}
for (int neighbor : adj_local[node]) {
if (!inS[neighbor]) {
pq.push({cost_local[neighbor], neighbor});
}
}
}
}
}
long long new_dp[MAXN];
for (int s = 0; s <= N; s++) {
new_dp[s] = dp[s];
}
for (int s1 = 0; s1 <= N; s1++) {
if (dp[s1] == INF) continue;
for (int s2 = 2; s2 <= L; s2++) {
if (comp_cost[s2] == INF) continue;
if (s1 + s2 > N) continue;
if (dp[s1] + comp_cost[s2] < new_dp[s1 + s2]) {
new_dp[s1 + s2] = dp[s1] + comp_cost[s2];
}
}
}
for (int s = 0; s <= N; s++) {
dp[s] = new_dp[s];
}
}
int Q;
cin >> Q;
while (Q--) {
long long S;
cin >> S;
int ans = 0;
for (int s = N; s >= 0; s--) {
if (dp[s] <= S) {
ans = s;
break;
}
}
cout << ans << '\n';
}
return 0;
}
