#include <bits/stdc++.h> using namespace std; #define MOD1 1000000007 #define MOD2 998244353 #define fir first #define sec second #define pushf push_front #define pushb push_back #define popf pop_front #define popb pop_back #define mp make_pair #define all(a) a.begin(), a.end() #define lbound(v, x) lower_bound(all(v), x) - v.begin() #define ubound(v, x) upper_bound(all(v), x) - v.begin() #define chmax(a, b) a = max(a, b) #define chmin(a, b) a = min(a, b) #define FOR1(a) for (int _ = 0; _ < (a); ++_) #define FOR2(i, a) for (int i = 0; i < (a); ++i) #define FOR3(i, a, b) for (int i = (a); i < (b); ++i) #define RFOR1(a) for (int _ = (a)-1; _ >= 0; --_) #define RFOR2(i, a) for (int i = (a)-1; i >= 0; --i) #define RFOR3(i, a, b) for (int i = (b)-1; i >= (a); --i) #define overload3(a, b, c, d, ...) d #define REP(...) overload3(__VA_ARGS__, FOR3, FOR2, FOR1)(__VA_ARGS__) #define RREP(...) overload3(__VA_ARGS__, RFOR3, RFOR2, RFOR1)(__VA_ARGS__) typedef long long ll; typedef pair<int, int> pii; typedef vector<int> vi; typedef pair<ll, ll> pll; typedef vector<ll> vll; typedef vector<bool> vb; typedef vector<char> vc; typedef vector<string> vs; typedef vector<pii> vpii; typedef vector<pll> vpll; typedef vector<vi> vvi; typedef vector<vll> vvll; typedef vector<vb> vvb; typedef vector<vc> vvc; typedef vector<vpii> vvpii; typedef vector<vpll> vvpll; typedef queue<int> qi; typedef queue<ll> qll; typedef queue<pii> qpii; typedef queue<pll> qpll; typedef deque<int> dqi; typedef deque<ll> dqll; typedef deque<pii> dqpii; typedef deque<pll> dqpll; typedef priority_queue<int> pqi; typedef priority_queue<ll> pqll; typedef priority_queue<pii> pqpii; typedef priority_queue<pll> pqpll; typedef priority_queue<int, vi, greater<int> > r_pqi; typedef priority_queue<ll, vll, greater<ll> > r_pqll; typedef priority_queue<pii, vpii, greater<pii> > r_pqpii; typedef priority_queue<pll, vpll, greater<pll> > r_pqpll; const ll inf = 1e16; int n, m; vll C; vi siz; vvi adj; vector<vector<array<ll, 3>>> dp; void dfs(int u, int p) { siz[u] = 1; for(int v : adj[u]) { if(v == p) continue; dfs(v, u); siz[u] += siz[v]; } } void solve(int u, int p) { int sz = 1; // cerr<<u<<' '; dp[u] = vector<array<ll, 3>> (siz[u]+1, {inf, inf, inf}); dp[u][0] = {0, C[u], inf}; for(int v : adj[u]) { if(v == p) continue; solve(v, u); RREP(i, sz+1) { // cerr<<u<<' '<<i<<' '<<dp[u][i].fir<<endl; RREP(j, siz[v]+1) { if(j != 0) { chmin(dp[u][i+j][0], dp[u][i][0] + *min_element(all(dp[v][j]))); chmin(dp[u][i+j][1], dp[u][i][1] + dp[v][j][0]); chmin(dp[u][i+j][2], dp[u][i][2] + min(dp[v][j][0], dp[v][j][2])); } if(i+j+1 <= siz[u]) { chmin(dp[u][i+j+1][2], dp[u][i][1] + dp[v][j][2]); chmin(dp[u][i+j+1][2], dp[u][i][2] + dp[v][j][1]); } if(i+j+2 <= siz[u]) { // if(u == 1 && i+j+2 == 3) { // cerr<<"E: "<<dp[u][i+j+2][2]<<endl; // } // if(dp[u][i][1] + dp[v][j][1] == 2) { // cerr<<"Error: "<<u<<' '<<v<<' '<<dp[u][i+j+2][2]<<' '<<i<<' '<<j<<' '<<dp[u][i][1]<<' '<<dp[v][j][1]<<endl; // } chmin(dp[u][i+j+2][2], dp[u][i][1] + dp[v][j][1]); } } } sz += siz[v]; // cerr<<u<<endl; // REP(j, siz[u]+1) { // cerr<<(dp[u][j][0] == inf ? -1 : dp[u][j][0])<<' '<<(dp[u][j][1] == inf ? -1 : dp[u][j][1])<<' '<<(dp[u][j][2] == inf ? -1 : dp[u][j][2])<<"; "; // } // cerr<<endl; } return; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m; C.resize(n+1); siz.resize(n+1, -1); adj.resize(n+1); dp.resize(n+1); REP(i, 1, n+1) { cin>>C[i]; } REP(i, m) { int a, b; cin>>a>>b; adj[a].pushb(b); adj[b].pushb(a); } REP(i, 1, n+1) { if(siz[i] == -1) { dfs(i, 0); adj[0].pushb(i); } } siz[0] = n+1; solve(0, -1); // REP(u, n+1) { // // cerr<<siz[i]<<' '<<dp[i].size()<<endl; // REP(j, siz[u]+1) { // cerr<<(dp[u][j][0] == inf ? -1 : dp[u][j][0])<<' '<<(dp[u][j][1] == inf ? -1 : dp[u][j][1])<<' '<<(dp[u][j][2] == inf ? -1 : dp[u][j][2])<<"; "; // } // cerr<<endl; // } vll ans(n+1); ans[n] = dp[0][n][0]; RREP(i, n) { ans[i] = min(dp[0][i][0], ans[i+1]); } // REP(i, n+1) { // cerr<<ans[i]<<' '; // } // int ans = 0; int q; cin>>q; while(q--) { ll x; cin>>x; int pos = ubound(ans, x) - 1; cout<<pos<<endl; } }