#include <bits/stdc++.h> using namespace std; using ll = long long; #define pb push_back const ll inf = 1e15; const int maxn = 1e3+5; const int maxq = 2e5+10; int n,m,q; int dp[maxn][2][2]; vector<ll>d(maxn); vector<int>adj[maxn]; ll dpi[maxn][maxn]; ll dpo[maxn][maxn]; int subs[maxn]; pair<int,int>qry[maxq]; int ans[maxq]; ll pdpi[maxn]; ll pdpo[maxn]; void solve(int i, int parent = -1){ subs[i] = 1; if(i!= n){ for(int j: adj[i]){ if(j!=parent){ solve(j,i); subs[i] += subs[j]; } } } for(int k=0;k<=n;k++){ dpi[i][k] = dpo[i][k] = inf; } dpo[i][0] = 0; int tot = 0; pdpi[0] = inf; pdpo[0] = 0; for(int j: adj[i]){ if(j==parent) continue; for(int k=0;k<=tot+subs[j]; k++) dpi[i][k] = dpo[i][k] = inf; for(int a=0;a<=tot;a++){ for(int b=0;b<=subs[j];b++){ dpo[i][a+b] = min( dpo[i][a+b], pdpo[a] + min( dpi[j][b], dpo[j][b] ) ); dpi[i][a+b] = min( dpi[i][a+b], min( pdpo[a] + dpi[j][b], pdpi[a] + min( dpi[j][b], dpo[j][b] ) ) ); if(b > 0){ dpi[i][a+b] = min( dpi[i][a+b], min( pdpo[a], pdpi[a] ) + dpo[j][b-1] + d[j] ); } } } tot += subs[j]; for(int k=0;k<=tot;k++){ pdpi[k] = dpi[i][k]; pdpo[k] = dpo[i][k]; } } for(int k=tot;k>=0;k--) dpi[i][k+1] = min(inf, dpi[i][k] + d[i]); dpi[i][0] = inf; } int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for(int i=0;i<n;i++){ cin >> d[i]; dpi[i][0] = -1; } for(int i=0;i<m;i++){ int a,b; cin >> a >> b; a--, b--; adj[a].pb(b); adj[b].pb(a); } for(int i=0;i<n;i++){ if(dpi[i][0] == -1){ solve(i); adj[n].pb(i); } } d[n] = inf; solve(n); for(int i=n-1;i>=0;i--) dpo[n][i] = min(dpo[n][i], dpo[n][i+1]); cin >> q; for(int i=0;i<q;i++){ cin >> qry[i].first; qry[i].second = i; } sort(qry,qry+q); int ansi = 0; for(int i=0;i<q;i++){ while(ansi < n and dpo[n][ansi+1] <= qry[i].first) ansi++; ans[qry[i].second] = ansi; } for(int i=0;i<q;i++) cout<<ans[i]<<'\n'; }