#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "shortcut.h"
ll solve(int n, VL l, VL d, ll C) {
VL X(n);
X[0] = 0;
replr(i, 1, n-1) X[i] = X[i-1] + l[i-1];
auto can = [&](ll k) {
ll mxs, mns, mxd, mnd;
mxs = mxd = +1e18;
mns = mnd = -1e18;
replr(i, 0, n-1) replr(j, i+1, n-1) {
if (d[i] + d[j] + X[j] - X[i] <= k) continue;
ll a = X[i];
ll b = X[j];
ll c = k-C-d[i]-d[j];
if (c < 0) return false;
/*cout << "PAIR (" << i << ", " << j << ")" << endl;*/
/*cout << " " << a + b - c << " <= sum <= " << a + b + c << endl;*/
/*cout << " " << a - b - c << " <= dif <= " << a - b + c << endl;*/
/*cout << " polygon("*/
/* "(" << (a+b-c+a-b+c)/2 << ", " << (a+b-c-a+b-c)/2 << "),"*/
/* "(" << (a+b+c+a-b+c)/2 << ", " << (a+b+c-a+b-c)/2 << "),"*/
/* "(" << (a+b+c+a-b-c)/2 << ", " << (a+b+c-a+b+c)/2 << "),"*/
/* "(" << (a+b-c+a-b-c)/2 << ", " << (a+b-c-a+b+c)/2 << "))"*/
/* << endl;*/
/*cout << " " << d[i] + d[j] + x[j] - x[i] << " <= " << k << endl;*/
/*cout << endl;*/
setmax(mns, a + b - c);
setmin(mxs, a + b + c);
setmax(mnd, a - b - c);
setmin(mxd, a - b + c);
}
/*cout << "INTERSECTION: " << endl;*/
/*cout << " " << mns << " <= sum <= " << mxs << endl;*/
/*cout << " " << mnd << " <= dif <= " << mxd << endl;*/
/*cout << "polygon("*/
/* "(" << (mns+mxd)/2 << ", " << (mns-mxd)/2 << "),"*/
/* "(" << (mxs+mxd)/2 << ", " << (mxs-mxd)/2 << "),"*/
/* "(" << (mxs+mnd)/2 << ", " << (mxs-mnd)/2 << "),"*/
/* "(" << (mns+mnd)/2 << ", " << (mns-mnd)/2 << "))"*/
/* << endl;*/
/*cout << endl;*/
ll verx, very, vary;
verx = (mxs+mnd)/2;
very = (mxs-mnd)/2;
vary = (mns-mxd)/2;
int l, r;
l = lower_bound(all(X), verx) - X.begin();
r = upper_bound(all(X), verx) - 1 - X.begin();
for (ll y : X) if (vary <= y && y <= very) {
ll L = max(mnd + y, mns - y);
ll R = min(mxd + y, mxs - y);
while (l-1 >= 0 && X[l-1] >= L) l--;
while (l < X.size() && X[l] < L) l++;
while (r+1 < X.size() && X[r+1] <= R) r++;
while (r >= 0 && X[r] > R) r--;
if (l <= r) return true;
}
return false;
};
ll L = 0, R = 1e18;
while (L + 1 < R) {
ll m = (L + R) / 2;
if (can(m)) R = m;
else L = m;
}
return R;
}
ll find_shortcut(int n, VI l, VI d, int c) {
VL L, D;
rep(i, n) L.pb(l[i]), D.pb(d[i]);
return solve(n, L, D, c);
}
