#include "closing.h"
#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <cmath>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <bitset>
#include <cstring>
#include <unordered_map>
using namespace std;
typedef long long ll;
ll n, x, y, k;
vector<pair<ll, ll>> d[3007];
int max_score(int N, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W){
n = N, x = X, y = Y, k = K;
if(x > y)
swap(x, y);
vector<ll> w(n);
for(int i = 0; i < n - 1; i++){
d[U[i]].push_back({V[i], W[i]});
d[V[i]].push_back({U[i], W[i]});
w[min(U[i], V[i])] = W[i];
}
vector<ll> a(n), b(n), c(n);
for(int i = x - 1; i >= 0; i--)
a[i] = a[i + 1] + w[i];
for(int i = x + 1; i < n; i++)
a[i] = a[i - 1] + w[i - 1];
for(int i = y - 1; i >= 0; i--)
b[i] = b[i + 1] + w[i];
for(int i = y + 1; i < n; i++)
b[i] = b[i - 1] + w[i - 1];
for(int i = 0; i < n; i++)
c[i] = max(a[i], b[i]);
vector<ll> p1(n), p2(n), p3(n);
for(int i = 0; i < n; i++){
if(i != 0){
p1[i] = p1[i - 1],
p2[i] = p2[i - 1],
p3[i] = p3[i - 1];
}
p1[i] += a[i];
p2[i] += b[i];
p3[i] += c[i];
}
ll ans = 0;
for(int i = 0; i < n; i++){
vector<pair<ll, ll>> vec;
vector<ll> ind(n, -1);
for(int j = min((int)x, i - 1); j >= 0; j--)
vec.push_back({a[j], j});
for(int j = max((int)y, i + 1); j < n; j++)
vec.push_back({b[j], j});
sort(vec.begin(), vec.end());
for(int j = 0; j < (ll)(vec.size()); j++)
ind[vec[j].second] = j;
ll cur = -1, sum = 0, cnt = 0, non_del = 0;
if(i > x)
cnt += p1[i - 1] - p1[x];
if(i < y)
cnt += p2[y] - (i != 0 ? p2[i - 1] : 0);
// if(i == 3){
// for(auto j: vec)
// cout << j.first << ' ' << j.second << endl;
// }
for(int j = i; j < n; j++){
cnt += c[j];
if(j <= y)
cnt -= b[j];
// if(i == 3){
// cout << "cnt " << j << ' ' << cnt << endl;
// }
if(ind[j] != -1){
vec[ind[j]].second = -1;
if(ind[j] <= cur){
sum -= vec[ind[j]].first;
non_del--;
}
}
if(y < i || j < x)
continue;
while(cur + 1 < vec.size()){
if(vec[cur + 1].second == -1){
cur++;
continue;
}
if(cnt + vec[cur + 1].first + sum <= k){
sum += vec[cur + 1].first;
cur++;
non_del++;
}
else
break;
}
while(cur >= 0 && cnt + sum > k){
if(vec[cur].second == -1){
cur--;
continue;
}
sum -= vec[cur].first;
cur--;
non_del--;
}
if(cnt + sum <= k){
// cout << " !! " << i << ' ' << j << ' ' << cur << ' ' << sum << ' ' << non_del << endl;
ans = max(ans, (j - i + 1) * 2 + non_del);
// cout << " ANS " << i << ' ' << j << " CNT : " << cnt << endl;
// if(ans == 6){
// }
}
}
}
return ans;
}
/*
1
7 2 4 8
0 1 2
1 2 3
2 3 4
3 4 2
4 5 5
5 6 3
1
7 2 4 24
0 1 2
1 2 3
2 3 4
3 4 2
4 5 5
5 6 3
*/
