#include <bits/stdc++.h>
#define rep(a,b,c) for(int a=b; a<c; a++)
#define repr(a,b,c) for(int a=b-1; a>c-1; a--)
#define repa(a,b) for(auto a:b)
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define fi first
#define se second
using namespace std;
int max_score(int N, int X, int Y, ll K, vector<int> U, vector<int> V, vector<int> W){
ll nxt[N]{}, prv[N]{};
rep(i,0,N-1) nxt[i]=W[i], prv[i+1]=W[i];
int ans=0;
ll dis[N], disx[N], disy[N];
disx[X]=0;
disy[Y]=0;
rep(i,X+1,N) disx[i]=disx[i-1]+nxt[i-1];
repr(i,X,0) disx[i]=disx[i+1]+prv[i+1];
rep(i,Y+1,N) disy[i]=disy[i-1]+nxt[i-1];
repr(i,Y,0) disy[i]=disy[i+1]+prv[i+1];
rep(i,0,N) dis[i]=max(disx[i],disy[i]);
rep(i,0,N){
rep(j,0,N){
if(i>X || j<X) continue;
ll dis2[N]{}, sum=0;
int cont=0;
priority_queue<ll, vector<ll>, greater<ll>> pq;
rep(k,0,N) if(i<=k && k<=j) dis2[k]=disx[k], sum+=dis2[k], cont++;
rep(k,0,N){
if(i<=k && k<=j) pq.push(dis[k]-dis2[k]);
else pq.push(disy[k]-dis2[k]);
}
if(sum>K) continue;
while(pq.size()){
if(K>=sum+pq.top()) sum+=pq.top();
else break;
pq.pop();
cont++;
}
ans=max(ans,cont);
}
}
return ans;
}
