#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 < n; i1++) {
for (int j1 = i1; j1 < n; j1++) {
if (!(i1 <= x && x <= j1)) continue;
for (int i2 = 0; i2 < n; i2++) {
for (int j2 = i2; j2 < n; j2++) {
if (!(i2 <= y && y <= j2)) continue;
int L = max(i1, i2), R = min(j1, j2);
ll inter = L <= R ? (prefix[R+1] - prefix[L]) : 0LL;
ll s1 = (prefix[j1+1] - prefix[i1]), s2 = (prefix[j2+1] - prefix[i2]);
if (s1 + s2 + inter <= k) {
best = max(best, (j1 - i1 + 1) + (j2 - i2 + 1));
}
}
}
}
}
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();
}
