#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);

const lg N= 2e5+5;

vector<array<lg, 2>> adj[N];
vector<lg> o;
lg lim = 0;

void dfs(lg src, lg par = -1, lg path = 0)
{
	if(path > lim)	return;
	o.push_back(path);
	for(auto [it, c] : adj[src])
	{
		if(it == par)	continue;
		dfs(it, src, path+c);
	}
	return;
}

int max_score(int n, int x, int y, lg k, vector<int> u, vector<int> v, vector<int> w)
{
	int ans = 0;
	lg linear = 1;
	for(int i = 0; i < n-1; i++)
	{
		linear &= (i == u[i] && i+1 == v[i]);
	}
	x++, y++;
	if(!linear)
	{
		for(int i = 1; i <= n; i++)	adj[i].clear();
		o.clear();
		lim = k;
		for(int i = 0; i < n-1; i++)
		{
			adj[u[i]].push_back({v[i], w[i]});
			adj[v[i]].push_back({u[i], w[i]});
		}
		dfs(x);
		dfs(y);
		sort(o.begin(), o.end());
		for(auto it : o)
		{
			k -= it;
			if(k >= 0)	ans++;
			else	break;
		}
		return ans;
	}
	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+1);
				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;
}