#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
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<int,int>> se;
for (int i=x-1;i>=0;i--)
se.insert({abs(pre[x]-pre[i]),i});
for (int i=y+1;i<=0;i++)
se.insert({abs(pre[y]-pre[i]),i});
vector<vector<ll>> 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[0]+p.first,x[1],x[2]+1});
else
v.push_back({x[0]+p.first,x[1]+1,x[2]});
}
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;
ll 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][0],w=min(a,v[mid][1]),e=min(b,v[mid][2]);
q-=dis[x][0]-(w<x?dis[x-w-1][0]:0)+dis[y+e][1]-dis[y][1];
if (val+q<=k)
s=mid;
else
e=mid;
}
ans=max((ll)ans,y-j+1+i-x+1+v[s][1]-a+v[s][2]-b);
}
return ans;
}
