#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debug2(x, y) {cerr<<#x<<", "<<#y<<" = "<<x<<", "<<y<<"\n";}
#define pb push_back
#define all(x) x.begin(), x.end()
const ll INF=10000001000000000ll;
const int MAXN=100010;
int n, m, k;
ll L[MAXN], D[MAXN], X[MAXN], C, ans;
ll prefD[MAXN], suffD[MAXN];
ll X1, Y1, X2, Y2;
void AddRect(ll x, ll y, ll xx, ll yy){
X1=max(X1, x);
Y1=max(Y1, y);
X2=min(X2, xx);
Y2=min(Y2, yy);
}
bool Check(ll val){
X1=Y1=-INF;
X2=Y2=INF;
for (int i=1; i<=n; i++) for (int j=1; j<i; j++){
if (D[i]+D[j]+X[i]-X[j]<=val) continue ;
ll x=X[j], y=X[i], z=val-C-D[i]-D[j];
// cerr<<x<<" "<<y<<" "<<z<<"\n";
// debug(D[i]+D[j]+y-x)
AddRect(x+y-z, x-y-z, x+y+z, x-y+z);
}
for (int i=1; i<=n; i++){
ll y=X[i];
ll l=max(X1-y, Y1+y), r=min(X2-y, Y2+y);
int pos=lower_bound(X+1, X+n+1, l)-X;
if (pos<=n && X[pos]<=r) return 1;
}
return 0;
}
ll find_shortcut(int _n, vector<int> l, vector<int> d, int _C){
n=_n;
C=_C;
for (int i=1; i<n; i++) L[i]=l[i-1], X[i+1]=X[i]+L[i];
for (int i=1; i<=n; i++) D[i]=d[i-1];
for (int i=1; i<=n; i++) prefD[i]=max(D[i], L[i-1]+prefD[i-1]);
for (int i=n; i; i--) suffD[i]=max(D[i], suffD[i+1]+L[i]);
/*
debug(Check(50))
return 0;
*/
ll dwn=-1, up=INF;
while (up-dwn>1){
ll mid=(dwn+up)>>1;
if (Check(mid)) up=mid;
else dwn=mid;
}
return up;
}
