/* * @Author: MaxPhast * @File: test.cpp * @Date: 2026-02-09 15:05:09 */ #include <bits/stdc++.h> using namespace std; #define int long long #define ii pair <int , int> #define iii pair <int , ii> #define iiii pair <ii , ii> #define FOR(i , l , r) for(int i = (l) , _r = (r) ; i <= _r ; ++ i) #define FORD(i , r , l) for(int i = (r) , _l = (l) ; i >= _l ; -- i) #define ALL(vec) vec.begin() , vec.end() #define UNI(vec) sort(ALL(vec)) , vec.erase(unique(ALL(vec)) , vec.end()) #define pb push_back #define MASK(i) (1ll << i) #define BIT(mask , i) ((mask >> i) & 1ll) #define ON(mask , i) (mask | MASK(i)) #define OFF(mask , i) (mask & (~MASK(i))) #define TURN(mask , i) (mask ^ MASK(i)) #define BP(mask) __builtin_popcountll(mask) #define sqr(x) (1ll * (x) * (x)) #define fi first #define se second #define oo 1e18 #define time() cerr << " \n " << "Time elapsed : " << 1000.0 * clock() / CLOCKS_PER_SEC << "ms." #define IO(TASK) if(fopen(#TASK".INP" , "r")){freopen(#TASK".INP" , "r" , stdin); freopen(#TASK".OUT" , "w" , stdout);} template <class X , class Y> bool maxz(X &a , const Y b) { if(a < b) { a = b; return true; } return false; } template <class X , class Y> bool minz(X &a , const Y b) { if(a > b) { a = b; return true; } return false; } namespace MaxPhast { const int N = 1e3 + 5; int n , m , q; bool vist[N]; int a[N] , sz[N] , dp[N][N][2]; vector <int> g[N]; void loang(int u) { vist[u] = true; for(int &v : g[u]) if(!vist[v]) loang(v); } void dfs(int u , int pre) { FOR(j , 0 , n) FOR(k , 0 , 1) dp[u][j][k] = oo; dp[u][1][1] = a[u]; dp[u][0][0] = 0; sz[u] = 1; for(int &v : g[u]) if(v != pre) { dfs(v , u); FORD(su , sz[u] , 0) FOR(sv , 0 , sz[v]) { minz(dp[u][su + sv][0] , dp[u][su][0] + (sv > 1 ? dp[v][sv][0] : oo)); minz(dp[u][su + sv][0] , dp[u][su][0] + (sv > 1 ? dp[v][sv][1] : oo)); minz(dp[u][su + sv][1] , dp[u][su][1] + (sv > 1 ? dp[v][sv][0] : oo)); minz(dp[u][su + sv][1] , dp[u][su][1] + (sv >= 1 ? dp[v][sv][1] : oo)); } sz[u] += sz[v]; } } void solve() { cin >> n >> m; FOR(i , 1 , n) cin >> a[i]; FOR(i , 1 , m) { int u , v; cin >> u >> v; g[u].pb(v); g[v].pb(u); } FOR(u , 1 , n) if(!vist[u]) { g[0].pb(u); g[u].pb(0); loang(u); } dfs(0 , -1); cin >> q; while(q--) { int s; cin >> s; int res = 0; FORD(i , n , 2) if(dp[0][i][0] <= s) { res = i; break; } cout << res << "\n"; } } } signed main() { ios_base :: sync_with_stdio(false) ; cin.tie(nullptr) ; cout.tie(nullptr) ; MaxPhast :: solve(); time(); } /* */