#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
typedef long long ll;
struct Edge {
int v, w;
};
int n, x, y;
ll k;
vi xi, yi, wi;
vector<vector<Edge>> adj;
const ll INF = 4e18;
int disconnected() {
int ans = 0;
ll tl = 0;
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q;
q.push({0, x}), q.push({0, y});
vector<bool> vis(n, false);
while (tl <= k && !q.empty()) {
auto cur = q.top(); q.pop();
vis[cur.second] = true;
if (tl + cur.first > k) break;
tl += cur.first;
ans++;
for (auto &e : adj[cur.second]) {
if (vis[e.v]) continue;
q.push({cur.first + ll(e.w), e.v});
}
}
return ans;
}
int linear() {
int best = 0;
vector<ll> prefix(n+1, 0);
for (int i = 1; i < n; i++) prefix[i+1] += prefix[i] + wi[i - 1];
for (int i1 = 0; i1 <= x; i1++) {
for (int i2 = x; i2 < n; i2++) {
for (int j1 = 0; j1 <= y; j1++) {
for (int j2 = y; j2 < n; j2++) {
int amt = (i2 - i1 + 1) + (j2 - j1 + 1);
int jj = max(j1, i2 + 1);
ll c = (prefix[i2+1] - prefix[i1]) + (prefix[j2+1] - prefix[jj]);
if (c <= k) best = max(best, amt);
}
}
}
}
return best;
}
int max_score(int N, int X, int Y, ll K, vi U, vi V, vi W) {
n = N; x = X; y = Y; k = K; xi = U; yi = V; wi = W;
adj.assign(n, vector<Edge>());
for (int i = 0; i < n - 1; i++) {
adj[xi[i]].push_back(Edge{yi[i], wi[i]});
adj[yi[i]].push_back(Edge{xi[i], wi[i]});
}
// return disconnected();
return linear();
}
