#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];
	vector<lg> best[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];
	}
	for(int i = y; i <= n; i++)
	{
		lg gh = 0;
		for(int j = i; j <= n; j++)
		{
			gh += d[j];
			// cout << gh << ' ';
			best[i].push_back(gh);
		}
		// cout << '\n';
	}
	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]);
				if(sum > k)	continue;
				int idx = max(y, j);
				int g = upper_bound(best[idx].begin(), best[idx].end(), k-sum)-1-best[idx].begin();
				// cout << k-sum << ' ' << idx << ' ' << g << ' ' << z << '\n';
				ans = max(ans, j-i+g+idx-z+2);
			}
			mxm = fake2;
			sum = o2;
		}
		mxm = fake3;
		sum = o3;
	}
	return ans;
}