/*
ID: Victor Chen [mail_vi1]
PROG: Closing Time
LANG: C++
*/

#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>

#define INF 0x3f3f3f3f

using namespace std;

typedef long long ll;

const int Maxn = 2e5;

class Graph
{
    public:
        int cnt, head[Maxn+10];
        struct Edge
        {
            int to, nxt;
            ll val;
        }p[2*Maxn+10];

        int root;
        int dep[Maxn+10], fa[Maxn+10];
        ll val[Maxn+10];

        void AddEdge(int x, int y, ll v)
        {
            cnt++;
            p[cnt].to = y;
            p[cnt].val = v;

            p[cnt].nxt = head[x];
            head[x] = cnt;
        }

        void dfs(int x)
        {
            for(int i=head[x]; i!=0; i=p[i].nxt)
                if(dep[p[i].to] == 0)
                {
                    dep[p[i].to] = dep[x] + 1;
                    fa[p[i].to] = x;
                    val[p[i].to] = val[x] + p[i].val;
                    dfs(p[i].to);
                }
        }

        void clear()
        {
            cnt = 0;
            memset(head, 0, sizeof(head));
        }

        void init(int x)
        {
            root = x;
            memset(dep, 0, sizeof(dep));
            dep[root] = 1;
            fa[root] = 0;
            val[root] = 0;

            dfs(root);
        }
}g;

class SegTree
{
    public:
        int cnt, root;
        struct Node
        {
            int l, r;
            int val, ch[2];

            ll sum;
        }p[Maxn*20];

        int build(int l, int r)
        {
            cnt++;
            p[cnt].l = l, p[cnt].r = r;
            p[cnt].val = p[cnt].ch[0] = p[cnt].ch[1] = p[cnt].sum = 0;
            return cnt;
        }

        void buildtree(int l, int r)
        {
            cnt = 0;
            root = build(l, r);
        }

        void modify(int x, int k, int v)
        {
            if(p[x].l == p[x].r)
            {
                p[x].val += v;
                p[x].sum += p[x].l * v;
                return;
            }

            int mid = (p[x].l+p[x].r)/2;
            if(k <= mid)
            {
                if(!p[x].ch[0]) p[x].ch[0] = build(p[x].l, mid);
                modify(p[x].ch[0], k, v);
            }
            else
            {
                if(!p[x].ch[1]) p[x].ch[1] = build(mid+1, p[x].r);
                modify(p[x].ch[1], k, v);
            }

            p[x].val = p[p[x].ch[0]].val + p[p[x].ch[1]].val;
            p[x].sum = p[p[x].ch[0]].sum + p[p[x].ch[1]].sum;
        }

        int find_cnt_below_k(int x, ll k)
        {
            if(k >= p[x].sum)
                return p[x].val;
            if(p[x].l == p[x].r)
                return min((int)(k/p[x].l), p[x].val);
            if(x == 0 || k == 0)
                return 0;

            if(p[x].ch[0])
            {
                if(k == p[p[x].ch[0]].sum) return p[p[x].ch[0]].val;
                else if(k < p[p[x].ch[0]].sum) return find_cnt_below_k(p[x].ch[0], k);
                else return p[p[x].ch[0]].val + find_cnt_below_k(p[x].ch[1], k-p[p[x].ch[0]].sum);
            }
            else
                return find_cnt_below_k(p[x].ch[1], k);
        }
}tree;

int n;
int c1, c2;

ll cst;

ll val[Maxn+10];

priority_queue<ll, vector<ll>, greater<ll>> q;

ll dis[Maxn+10];
ll dis1[Maxn+10], dis2[Maxn+10];

struct Node
{
    int id;
    ll cst1, cst2;
    
    bool operator < (const Node &x) const
    {
        return cst2 < x.cst2;
    }

    void build(int id, ll x, ll y)
    {
        this->id = id;
        this->cst1 = min(x, y);
        this->cst2 = max(x, y);
    }
}p[Maxn+10];

int inQueue = 0;

ll cur[Maxn+10];
int max_score(int N, int X, int Y, ll K, vector<int> U, vector<int> V, vector<int> W)
{
    tree.buildtree(0, 1e6);

    int ans1 = 0, ans2 = 0;

    n = N, c1 = X+1, c2 = Y+1;
    for(int i=0; i<n-1; i++)
        dis[i+1] = W[i];
    
    if(c1 > c2) swap(c1, c2);

    // Case 1: If not connected.
    dis1[c1] = 0;
    for(int i=c1-1; i>=1; i--)
        dis1[i] = dis1[i+1] + dis[i];
    for(int i=c1+1; i<=n; i++)
        dis1[i] = dis1[i-1] + dis[i-1];
    dis2[c2] = 0;
    for(int i=c2-1; i>=1; i--)
        dis2[i] = dis2[i+1] + dis[i];
    for(int i=c2+1; i<=n; i++)
        dis2[i] = dis2[i-1] + dis[i-1];
    for(int i=1; i<=n; i++)
        val[i] = min(dis1[i], dis2[i]);
    sort(val+1, val+n+1);
    cst = 0;
    for(int i=1; i<=n; i++)
        if(cst + val[i] <= K)
            cst += val[i], ans1++;
        else
            break;

    for(int i=1; i<=n; i++)
        p[i].build(i, dis1[i], dis2[i]);
    
    inQueue = 0;
    sort(p+1, p+n+1);
    for(int i=1; i<=n; i++)
    {
        if(c1 <= i && i <= c2)
        {
            tree.modify(1, p[i].cst2-p[i].cst1, 1);
            K -= p[i].cst1;
            inQueue++;
        }
        else
            tree.modify(1, p[i].cst1, 1);
        
        // printf("Inserted: %d\n", p[i].cst1);
    }

    if(K < 0) return ans1;

    ans2 = max(ans2, inQueue + tree.find_cnt_below_k(1, K));

    for(int i=1; i<=n; i++)
    {
        if(c1 <= i && i <= c2)
            continue;

        tree.modify(1, p[i].cst1, -1);
        // printf("Deleted: %d\n", p[i].cst1);

        tree.modify(1, p[i].cst2-p[i].cst1, 1);
        // printf("Inserted: %d\n", p[i].cst2-p[i].cst1);

        K -= p[i].cst1;
        inQueue++;

        if(K < 0)
            break;

        ans2 = max(ans2, tree.find_cnt_below_k(1, K) + inQueue);

        printf("%d: %d\n", K, tree.find_cnt_below_k(1, K));
    }

    return max(ans1, ans2);
}

// int T;
// int N, X, Y;
// ll K;
// vector<int> U, V, W;

// int main()
// {
//     scanf("%d", &T);
//     while(T != 0)
//     {
//         T--;
//         scanf("%d%d%d%lld", &N, &X, &Y, &K);
//         U.clear(); V.clear(); W.clear();
//         for(int i=0; i<N-1; i++)
//         {
//             int x, y, z;
//             scanf("%d%d%d", &x, &y, &z);
//             U.push_back(x); V.push_back(y); W.push_back(z);
//         }

//         printf("%d\n", max_score(N, X, Y, K, U, V, W));
//     }

//     return 0;
// }