#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,m,n) for(int i=m; i<=n; i++)
#define reb(i,m,n) for(int i=m; i>=n; i--)
#define iter(id, v) for (auto id : v)
#define ii pair<int,int>
#define fs first
#define se second
#define pb push_back
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(), v.end()
#define bit(msk, i) ((msk >> i) & 1)
#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);
#define el cout <<"\n"
template<typename A, typename B> ostream& operator<<(ostream& out, const pair<A, B> &v) { out << "(" << v.fs <<"," << v.se << ") "; return out; }
#ifndef ONLINE_JUDGE
#include "debug.h"
#else
#define deb(...) 23
#define ___
#define n____
#endif
mt19937 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }
const ll N = 1e3 + 7;
const ll Mod = 1e9 + 7;
const ll bse = 137;
const ll szBL = 650;
const ll INF = 1e18;
int n, m, Q;
ll D[N];
vector<int> ke[N];
int subtree[N];
int dd[N];
ll dp[N][N][2], f[N][N][2];
int nn;
ll pre[N];
ii qr[N];
inline void minimize(ll &a, ll b) { if (a > b) a = b; }
void dfs (int u, int pa) {
vector<int> Ch = {0};
subtree[u] = 1, dd[u] = 1;
iter (&v, ke[u]) {
if (v != pa) {
// deb(u, v);
dfs(v, u);
subtree[u] += subtree[v];
Ch.pb(v);
}
}
int nC = SZ(Ch) - 1;
rep (i, 0, nC) {
deb(u, Ch[i]);
}
rep (i, 0, nC)
rep (j, 0, subtree[u]) {
f[i][j][0] = f[i][j][1] = INF;
}
int tot = 1;
f[0][0][0] = 0;
f[0][0][1] = D[u];
rep (i, 1, nC) {
int &curC = Ch[i];
rep (k, 0, tot)
rep (t, 0, subtree[curC]) {
minimize(f[i][k + t][0], f[i - 1][k][0] + min(dp[curC][t][1], dp[curC][t][0]));
if (k) {
minimize(f[i][k + t][1], f[i - 1][k - 1][0] + dp[curC][t][1] + D[u]);
if (t) {
minimize(f[i][k + t][1], f[i - 1][k - 1][0] + dp[curC][t - 1][0] + D[curC] + D[u]);
}
}
f[i][k + t][1] = min({f[i][k + t][1],
f[i - 1][k][1] + dp[curC][t][1],
f[i - 1][k][1] + dp[curC][t][0]});
if (t) {
minimize(f[i][k + t][1], f[i - 1][k][1] + dp[curC][t - 1][0] + D[curC]);
}
}
tot += subtree[curC];
}
rep (k, 0, subtree[u]) {
dp[u][k][0] = f[nC][k][0];
dp[u][k][1] = f[nC][k][1];
}
}
void chloe_solution() {
cin >> n >> m;
D[0] = INF;
rep (i, 1, n) cin >> D[i];
rep (i, 1, m) {
ll u, v;
cin >> u >> v;
ke[u].pb(v);
ke[v].pb(u);
}
rep (i, 1, n) {
if (dd[i] == 0) {
dfs(i, 0);
ke[0].pb(i);
ke[i].pb(0);
}
}
dfs(0, 0);
reb (i, n, 0) {
minimize(dp[0][i][0], dp[0][i + 1][0]);
}
cin >> Q;
rep (qi, 1, Q) {
cin >> qr[qi].fs;
qr[qi].se = qi;
}
sort (qr + 1, qr + 1 + Q);
vector<int> ans(Q + 2);
ll cur = 0;
rep (qi, 1, Q) {
while (cur <= n && dp[0][cur][0] <= qr[qi].fs) ++cur;
ans[qr[qi].se] = cur - 1;
}
rep (i, 1, Q) cout << ans[i] <<"\n";
}
int main() {
// file("c");
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll num_Test = 1;
// cin >> num_Test;
while(num_Test--)
chloe_solution();
}
/*
*/
Compilation message
dzumbus.cpp:22:14: fatal error: debug.h: No such file or directory
22 | #include "debug.h"
| ^~~~~~~~~
compilation terminated.
