#include "closing.h"

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

int max_score(int N, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    using data = tuple<ll, int, int, int>;
    priority_queue<data, vector<data>, greater<data>> pq;
    vector<ll> dx(N, 0), dy(N, 0);

    for(int i = X + 1; i < N; ++i) dx[i] = dx[i-1] + W[i-1];
    for(int i = X - 1; i >= 0; --i) dx[i] = dx[i+1] + W[i];

    for(int i = Y + 1; i < N; ++i) dy[i] = dy[i-1] + W[i-1];
    for(int i = Y - 1; i >= 0; --i) dy[i] = dy[i+1] + W[i];

    vector<ll> sx(N, 0LL), sy(N, 0LL), sxy(N, 0LL);
    sx[0] = dx[0];
    sy[0] = dy[0];
    sxy[0] = max(dx[0], dy[0]);

    for(int i = 1; i < N; ++i) {
        sx[i] = sx[i - 1] + dx[i];
        sy[i] = sy[i - 1] + dy[i];
        sxy[i] = sxy[i - 1] + max(dx[i], dy[i]);
    }

    const auto gs = [&](vector<ll> &s, int l, int r) -> ll {
        if(l > r) return 0LL;
        return s[r] - (l ? s[l - 1] : 0LL);
    };

    int ans = 0;
    for(int i = 0; i < N; ++i) {
        for(int j = i; j < N; ++j) {
            if(i > X || j < X) continue;

            for(int k = 0; k < N; ++k) {
                if(k < i) continue;
                for(int l = k; l < N; ++l) {
                    if(j > l) continue;
                    if(k > Y || l < Y) continue;

                    int cnt = j - i + 1 + l - k + 1;
                    ll res = 0;             

                    // [i, j] [k, l]
                    if(j < k) {
                        res += gs(sx, i, j) + gs(sy, k, l);
                    }
                    else {
                        res += gs(sx, i, k - 1) + gs(sy, j + 1, l);
                        res += gs(sxy, k, j);
                    }

                    if(res <= K) ans = max(ans, cnt);

                }
            }
        }
    }

    return ans;
}