#include <bits/stdc++.h>
#ifndef CYBER
#include "closing.h"
#endif
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast")

using namespace std;
using namespace __gnu_pbds;

#define lg long long
#define ordered_set	tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

int max_score(int n, int x, int y, lg k, vector<int> u, vector<int> v, vector<int> w)
{
	int ans = 0;
	x++, y++;
	lg a[n+2], b[n+2], c[n+2], d[n+2];
	memset(a, 0, sizeof(a));
	memset(b, 0, sizeof(b));
	memset(c, 0, sizeof(c));
	memset(d, 0, sizeof(d));
	for(int i = x-1; i >= 1; i--)
	{
		a[i] = a[i+1]+w[i-1];
	}
	for(int i = y-1; i >= 1; i--)
	{
		c[i] = c[i+1]+w[i-1];
	}
	for(int i = x+1; i <= n; i++)
	{
		b[i] = b[i-1]+w[i-2];
	}
	for(int i = y+1; i <= n; i++)
	{
		d[i] = d[i-1]+w[i-2];
	}
	lg sum = 0;
	vector<lg> mxm(n+2);
	for(int i = x; i >= 1; i--)
	{
		sum += max(0ll, a[i]-mxm[i]);
		mxm[i] = max(mxm[i], a[i]);
		vector<lg> fake3 = mxm;
		lg o3 = sum;
		for(int j = x; j <= n; j++)
		{
			sum += max(0ll, b[j]-mxm[j]);
			mxm[j] = max(mxm[j], b[j]);
			vector<lg> fake2 = mxm;
			lg o2 = sum;
			for(int z = y; z >= 1; z--)
			{
				sum += max(0ll, c[z]-mxm[z]);
				mxm[z] = max(mxm[z], c[z]);
				lg rem = k-sum, beg = max({y, z, j, i});
				int l = max({y, z, j, i}), r = n;
				while(l <= r)
				{
					int mid = (l+r)/2;
					if(d[mid]-d[beg-1] > rem)
					{
						r = mid-1;
					}
					else{
						l = mid+1;
						ans = max(ans, j-i+1+mid-z+1);
					}
				}
			}
			mxm = fake2;
			sum = o2;
		}
		mxm = fake3;
		sum = o3;
	}
	return ans;
}