#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
int max_score(int n, int x, int y, ll k,vector<int> U, vector<int> V, vector<int> W)
{
ll pre[n]={};
for (int i=1;i<n;i++)
pre[i]=pre[i-1]+W[i-1];
ll dis[n][2],mn[n];
dis[0][0]=abs(pre[x]-pre[0]),dis[0][1]=abs(pre[y]-pre[0]);
mn[0]=min(dis[0][0],dis[0][1]);
for (int i=1;i<n;i++)
dis[i][0]=abs(pre[x]-pre[i])+dis[i-1][0],
dis[i][1]=abs(pre[y]-pre[i])+dis[i-1][1],
mn[i]=mn[i-1]+min(abs(pre[x]-pre[i]),abs(pre[y]-pre[i]));
set<pair<ll,int>> se;
for (int i=x-1;i>=0;i--)
se.insert({abs(pre[x]-pre[i]),i});
for (int i=y+1;i<n;i++)
se.insert({abs(pre[y]-pre[i]),i});
vector<pair<ll,pair<int,int>>> v;
v.push_back({0,{0,0}});
while (!se.empty())
{
auto p=*se.begin();se.erase(p);
auto x=v.back();
if (p.second>y)
v.push_back({x.ff+p.ff,{x.ss.ff,x.ss.ss+1}});
else
v.push_back({x.ff+p.ff,{x.ss.ff+1,x.ss.ss}});
}
int ans=0;
for (int i=x;i<n;i++)
for (int j=y;j>=0;j--)
{
ll val=dis[i][0]-dis[x][0]+dis[y][1]-(j?dis[j-1][1]:0);
if (i>j)
val-=mn[min(y,i)]-(j||x?mn[max(j,x)-1]:0);
if (val>k) continue;
int a=max(0,x-j),b=max(0,i-y);
int s=0,e=v.size();
while (s+1<e)
{
int mid=(s+e)/2;
ll q=v[mid].ff,w=min(a,v[mid].ss.ff),r=min(b,v[mid].ss.ss);
q-=dis[x][0]-(w<x?dis[x-w-1][0]:0)+dis[y+r][1]-dis[y][1];
if (val+q<=k)
s=mid;
else
e=mid;
}
ans=max(ans,y-j+1+i-x+1+v[s].ss.ff+v[s].ss.ss);
}
return ans;
}
