#include <bits/stdc++.h>
#include "shortcut.h"
using namespace std;
long long sum[1000000];
long long val[3000][3000];
const long long INF=1e16;
int c;
long long pl[1000000];
long long val2[3000];
int n;
bool isp(long long k) {
long long mmn=-INF;
long long mmx=INF;
long long pmn=-INF;
long long pmx=INF;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++) {
val[i][j]=INF;
}
}
for(int i=0;i<n;i++) {
for(int j=i+1;j<n;j++) {
if (sum[j]-sum[i]+pl[i]+pl[j]<=k) {
val[i][j]=INF;
}
else {
val[i][j]=k-c-pl[i]-pl[j];
mmn=max(mmn,sum[i]-sum[j]-val[i][j]);
mmx=min(mmx,sum[i]-sum[j]+val[i][j]);
pmn=max(pmn,sum[i]+sum[j]-val[i][j]);
pmx=min(pmx,sum[i]+sum[j]+val[i][j]);
}
}
}
for(int i=0;i<n;i++) {
for(int j=i+1;j<n;j++) {
if (sum[i]-sum[j]>=mmn&&sum[i]-sum[j]<=mmx&&sum[i]+sum[j]>=pmn&&sum[i]+sum[j]<=pmx) {
return true;
}
}
}
return false;
}
long long find_shortcut(int nn,vector<int> l,vector<int> d,int cc) {
n=nn;
c=cc;
sum[0]=0;
for(int i=0;i<n-1;i++) {
sum[i+1]=sum[i]+l[i];
}
for(int i=0;i<n;i++) {
pl[i]=d[i];
}
long long lo=0; //impossible
long long hi=1e16; //possible
while (lo+1<hi) {
long long mid=(lo+hi)/2;
if (isp(mid)) {
hi=mid;
}
else {
lo=mid;
}
}
return hi;
}
