#include<bits/stdc++.h> using namespace std; #define int long long const int maxn = 1e3 + 5, inf = 1e9; vector<int> g[maxn]; int dp[maxn][maxn][2][2], vis[maxn], val[maxn], sz[maxn]; void dfscc(int u){ vis[u] = 1; for(int v: g[u]) if(!vis[v]) dfscc(v); } //dp u c i j. subtree u chọn c thằng (u có chọn không(i)). (có được kết nối không(j)) void dfs(int u, int p){ for(int c = 0; c < maxn; c++) for(int i: {0, 1}) for(int j: {0, 1}) dp[u][c][i][j] = inf; dp[u][0][1][0] = val[u]; dp[u][0][0][0] = 0; sz[u] = 1; for(int v: g[u]){ if(v != p){ dfs(v, u); for(int sz1 = sz[u]; sz1 >= 0; sz1--){ for(int i1: {0, 1}){ for(int j1: {0, 1}){ for(int sz2 = sz[v]; sz2 >= 0; sz2--){ for(int i2: {0, 1}){ for(int j2: {0, 1}){ int nwu = u; int nwc = sz1 + sz2 + (i1 && i2) * ((j1 == 0) + (j2 == 0)); int nwi = i1; int nwj = j1 | (i1 && i2); dp[nwu][nwc][nwi][nwj] = min(dp[nwu][nwc][nwi][nwj], dp[u][sz1][i1][j1] + dp[v][sz2][i2][j2]); } } } } } } } sz[u] += sz[v]; } } signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; for(int i = 1; i <= n; i++) cin >> val[i]; for(int i = 1; i <= m; i++){ int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } for(int i = 1; i <= n; i++){ if(vis[i]) continue; dfscc(i); g[0].push_back(i); } dfs(0, -1); vector<int> res(n + 1); for(int i = n; i >= 0; i--) res[i] = dp[0][i][0][0]; for(int i = n - 1; i >= 0; i--) res[i] = min(res[i], res[i + 1]); int q; cin >> q; while(q--){ int s; cin >> s; cout << max(0LL, (int) (upper_bound(res.begin(), res.end(), s) - res.begin() - 1)) << "\n"; } }