#include <bits/stdc++.h>
using namespace std;
#include "closing.h"
//#define int long long
using ll = long long;
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll e[200005];
int max_score(int N, int X, int Y, long long K,
std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
ll x = X, y = Y;
vector <ll> v;
ll cur = 0;
for(int i = 0; i < N - 1; i++)e[i] = W[i];
for(int i = 1; i < N - 1; i++)e[i] += e[i - 1];
for(int i = x - 1; i >= 0; i--){
cur += W[i];
v.push_back(cur);
}
cur = 0;
for(int i = y + 1; i < N; i++){
cur += W[i - 1];
v.push_back(cur);
}
sort(v.begin(), v.end());
for(int i = 1; i < (int)v.size(); i++)v[i] += v[i - 1];
ll ans = 0;
ll tot = 0;
for(int i = x; i < N; i++){
tot += e[i] - e[x];
ll tmp = 0;
for(int j = y; j >= 0; j--){
tmp += e[y] - e[j];
if(i >= j)tmp -= min(e[y] - e[j], e[j] - e[x]);
int res = upper_bound(v.begin(), v.end(), K - tmp - tot) - v.begin();
if(K - tmp - tot >= 0)ans = max(ans, res + (j - y + 1) + (i - x + 1));
}
}
return ans;
}
