// In the name of Allah
#include <bits/stdc++.h>
#include "shortcut.h"
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<ld> cld;
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
#define F first
#define S second
#define pb push_back
#define sep ' '
#define endl '\n'
#define Mp make_pair
#define kill(x) cout << x << '\n', exit(0)
#define set_dec(x) cout << fixed << setprecision(x);
#define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 1500 + 4;
const ll oo = 1e18 + 4;
const int maxlg = 12;
int n; ll w;
ll A[maxn], D[maxn], A1[maxn], A2[maxn];
ll valx[maxn], valD[maxn]; ll M1[maxn][maxlg], M2[maxn][maxlg];
ll get_max1(int l, int r) {
if (r - l <= 0) return -oo;
int j = __lg(r - l);
return max(M1[l][j], M1[r - (1 << j)][j]);
}
ll get_max2(int l, int r) {
if (r - l <= 0) return -oo;
int j = __lg(r - l);
return max(M2[l][j], M2[r - (1 << j)][j]);
}
ll cal1(int i, int x, int l, int r) {
ll res = -oo;
if (x == 0) return res;
if (i - x >= l) {
res = max(res, A[i] + (D[i] + get_max2(i - x, i)));
}
else {
res = max(res, A[i] + (D[i] + get_max2(l, i))); x -= (i - l);
res = max(res, A[i] + (D[i] - D[l]) + w + (D[r] + get_max2(r - x + 1, r + 1)));
}
return res;
}
ll cal2(int i, int x, int l, int r) {
ll res = -oo;
if (x == 0) return res;
if (i + x <= r) {
res = max(res, A[i] + (get_max1(i + 1, i + x + 1) - D[i]));
}
else {
res = max(res, A[i] + (get_max1(i + 1, r + 1) - D[i])); x -= (r - i);
res = max(res, A[i] + (D[r] - D[i]) + w + (get_max1(l, l + x) - D[l]));
}
return res;
}
ll calD(int m, int i, int j) {
if (i == j) return -oo;
return min(valD[j] - valD[i], valD[i] + (valD[m - 1] - valD[j]) + w) + valx[i] + valx[j];
}
ll calR(int m, int l, int r) {
ll res = 0;
for (int i = 0; i < m; i++) {
res = max(res, max(max(calD(m, 0, i), calD(m, i, m - 1)), valx[i]));
}
int j = 0;
for (int i = m; i < 3 * m; i++, j++) {
if (j >= m) j -= m;
valx[i] = valx[j];
valD[i] = valD[(i - j) - 1] + w + valD[j];
}
j = 0;
for (int i = m; i < 2 * m; i++) {
j = max(j, i - m + 1);
while ((valD[i] - valD[j]) > (valD[j + m] - valD[i])) j++;
res = max(res, cal1(l + (i - m), (i - j), l, r));
res = max(res, cal2(l + (i - m), (j + m) - (i + 1), l, r));
}
return res;
}
ll calx(int l, int r) {
if (l == r) return max(A1[n - 1], A2[0]);
ll res = max(A1[l], A2[r]);
for (int i = l; i <= r; i++) {
valx[i - l] = A[i]; valD[i - l] = D[i] - D[l];
}
int m = (r - l + 1);
for (int i = 0; i < l; i++) valx[0] = max(valx[0], A[i] + (D[l] - D[i]));
for (int i = r + 1; i < n; i++) valx[m - 1] = max(valx[m - 1], A[i] + (D[i] - D[r]));
res = max(res, calR(m, l, r));
return res;
}
ll find_shortcut(int nx, vector<int> lx, vector<int> dx, int cx) {
n = nx; w = cx; D[0] = 0;
for (int i = 0; i < n; i++) A[i] = dx[i];
for (int i = 1; i < n; i++) D[i] = D[i - 1] + lx[i - 1];
for (int i = n - 1; i >= 0; i--) {
M1[i][0] = A[i] + D[i];
M2[i][0] = A[i] - D[i];
for (int j = 1; j < maxlg; j++) {
if (i + (1 << j) - 1 >= n) break;
M1[i][j] = max(M1[i][j - 1], M1[i + (1 << (j - 1))][j - 1]);
M2[i][j] = max(M2[i][j - 1], M2[i + (1 << (j - 1))][j - 1]);
}
}
ll mx = -oo;
for (int i = 0; i < n; i++) {
A1[i] = max(A[i], (A[i] + D[i]) + mx);
if (i - 1 >= 0) A1[i] = max(A1[i], A1[i - 1]);
mx = max(mx, A[i] - D[i]);
}
mx = -oo;
for (int i = n - 1; i >= 0; i--) {
A2[i] = max(A[i], (A[i] - D[i]) + mx);
if (i + 1 < n) A2[i] = max(A2[i], A2[i + 1]);
mx = max(mx, A[i] + D[i]);
}
ll ans = oo;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
ans = min(ans, calx(i, j));
}
}
return ans;
}
