#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> segTree(8e5), lazy(8e5);
void pushDown(int cur, int left, int right) {
if (!lazy[cur]) return;
segTree[cur] += lazy[cur];
if (left != right) {
lazy[cur * 2] += lazy[cur];
lazy[cur * 2 + 1] += lazy[cur];
}
lazy[cur] = 0;
}
void update(int cur, int left, int right, int tLeft, int tRight, ll val) {
pushDown(cur, left, right);
if (tRight < left || tLeft > right) return;
if (tLeft <= left && tRight >= right) {
lazy[cur] = val;
pushDown(cur, left, right);
return;
}
int mid = (left + right) / 2;
update(cur * 2, left, mid, tLeft, tRight, val);
update(cur * 2 + 1, mid + 1, right, tLeft, tRight, val);
segTree[cur] = segTree[cur * 2] + segTree[cur * 2 + 1];
}
pair<ll, int> treeWalk(int cur, int left, int right, ll val) {
pushDown(cur, left, right);
if (val >= segTree[cur]) return {segTree[cur], right - left + 1};
if (left == right) return {0, 0};
int mid = (left + right) / 2;
auto res = treeWalk(cur * 2, left, mid, val);
if (val > segTree[cur * 2]) {
auto res2 = treeWalk(cur * 2 + 1, mid + 1, right, val - segTree[cur * 2]);
res.first += res2.first;
res.second += res2.second;
}
return res;
}
int max_score(int N, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
segTree.clear();
lazy.clear();
segTree.assign(8e5, 0);
lazy.assign(8e5, 0);
vector<ll> xReach(N, 0), yReach(N, 0);
auto get = [&](int a, int b) {
return W[min(a, b)];
};
auto preComp = [&] () {
ll cur = 0;
for (int i = X + 1; i < N; ++i) {
cur += get(i - 1, i);
xReach[i] = cur;
}
cur = 0;
for (int i = X - 1; i >= 0; --i) {
cur += get(i, i + 1);
xReach[i] = cur;
}
cur = 0;
for (int i = Y + 1; i < N; ++i) {
cur += get(i - 1, i);
yReach[i] = cur;
}
cur = 0;
for (int i = Y - 1; i >= 0; --i) {
cur += get(i, i + 1);
yReach[i] = cur;
}
};
preComp();
int res = 2;
// vector<ll> preSum(Y - X);
// for (int i = 1; i < Y - X; ++i) preSum[i] = preSum[i - 1] + xReach[i + X], update(1, 1, Y - X - 1, i, i, preSum[i]);
// vector<ll> modelSeg(N * 4 + 1), modelLazy(N * 4 + 1);
// for (int i = 1; i <= 4 * N; ++i) modelSeg[i] = segTree[i], modelLazy[i] = lazy[i];
// for (auto &i : xReach) cout << i << ' ';
// cout << endl;
// for (auto &i : yReach) cout << i << ' ';
// cout << endl;
for (int left = 0; left <= X; ++left) {
for (int right = N - 1; right >= Y; --right) {
ll curCost = 0;
int curRes = 2;
for (int i = left; i < X; ++i) {
++curRes;
curCost += xReach[i];
}
for (int i = right; i > Y; --i) {
++curRes;
curCost += yReach[i];
}
// cout << left << ' ' << right << ' ' << curCost << ' ' << curRes << endl;
for (int y = Y; y >= left; --y) {
if (curCost > K) break;
// cout << y << ' ';
ll curRemain = K - curCost;
// cout << curRemain << ' ';
int cnt = 0;
for (int i = X + 1; i < Y; ++i) {
int curNeed = xReach[i];
if (y <= i) curNeed = max(0ll, xReach[i] - yReach[i]);
if (curRemain < curNeed) break;
curRemain -= curNeed;
++cnt;
}
// auto [cost, cnt] = treeWalk(1, 1, Y - X - 1, curRemain);
// curRemain -= cost;
if (cnt == Y - X - 1) cnt += min(curRemain / xReach[Y], (ll)right - Y + 1);
// cout << cnt << endl;
res = max(res, curRes + cnt);
if (y > X) curCost += yReach[y - 1], ++curRes;
else if (y > left) curCost += max(0ll, yReach[y - 1] - xReach[y - 1]), ++curRes;
}
// for (int y = Y; y >= left; --y) {
// if (curCost > K) break;
// ll curRemain = K - curCost;
// auto [cost, cnt] = treeWalk(1, 1, Y - X - 1, curRemain);
// curRemain -= cost;
// if (cnt == Y - X - 1) cnt += min(curRemain / xReach[Y], (ll)right - Y + 1);
// res = max(res, curRes + cnt);
// if (y) curCost += yReach[y - 1], ++curRes;
// if (y > X + 1) update(1, 1, Y - X - 1, y - X - 1, Y - X - 1, min(xReach[y - 1], yReach[y - 1]));
// }
// for (int i = 1; i <= 4 * N; ++i) segTree[i] = modelSeg[i], lazy[i] = modelLazy[i];
}
}
return res;
}
