#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<bool> vx(N, false), vy(N, false);
    int ans = 2;

    vx[X] = vy[Y] = true;
    vector<int> dir = {-1, 1};

    for(auto &d : dir) {
        if(X + d < 0 || X + d >= N) continue;
        pq.emplace(dx[X+d], X+d, 0, 1);
    }

    for(auto &d : dir) {
        if(Y + d < 0 || Y + d >= N) continue;
        pq.emplace(dy[Y+d], Y+d, 0, 2);
    }

    ll tot = 0;

    for(; !pq.empty(); ) {
        auto [cost, cur, state, app] = pq.top();
        pq.pop();

        int mask = (vx[cur] ? 1 : 0) + (vy[cur] ? 2 : 0);
        if(mask != state) continue;

        if(tot + cost > K) break;
        tot += cost;
        ++ans;

        if(app == 1) {
            vx[cur] = true;
            for(auto &d : dir) {
                if(cur + d < 0 || cur + d >= N || vx[cur + d]) continue;
                ll nxt = (vy[cur + d] ? max(0LL, dy[cur + d] - dx[cur + d]) : dy[cur + d]);
                int msk = (vy[cur + d] ? 2 : 0);
                pq.emplace(nxt, cur + d, msk, 1);
            }
        }
        else {
            vy[cur] = true;
            for(auto &d : dir) {
                if(cur + d < 0 || cur + d >= N || vy[cur + d]) continue;
                ll nxt = (vx[cur + d] ? max(0LL, dx[cur + d] - dy[cur + d]) : dx[cur + d]);
                int msk = (vx[cur + d] ? 1 : 0);
                pq.emplace(nxt, cur + d, msk, 2);
            }
        }
    }

    return ans;
}