#include "shortcut.h"
#include<bits/stdc++.h>
using namespace std;
const long long maxn=1000000+10;
long long inf=1e16,n,c;
long long all[maxn],alld[maxn],ps[maxn],l1,l2,r1,r2;
void addr(long long x1,long long y1,long long x2,long long y2){
long long fx=x1+y1;
long long fy=x1-y1;
x1=fx;
y1=fy;
fx=x2+y2;
fy=x2-y2;
x2=fx;
y2=fy;
l1=max(l1,x1);
l2=min(l2,x2);
r1=max(r1,y2);
r2=min(r2,y1);
}
bool dakh(long long x,long long y){
long long fx=x+y;
long long fy=x-y;
x=fx;
y=fy;
if(x>=l1&&x<=l2&&y>=r1&&y<=r2){
return 1;
}
return 0;
}
bool check(long long mid){
l1=r1=-inf;
l2=r2=inf;
for(long long j=1;j<=n;j++){
for(long long i=j+1;i<=n;i++){
if(ps[i]-ps[j]+alld[i]+alld[j]>mid){
addr(ps[i],-mid+c+alld[i]+alld[j]+ps[j],ps[i],mid-c-alld[i]-alld[j]+ps[j]);
}
}
}
set<long long>st;
for(long long i=1;i<=n;i++){
st.insert(ps[i]);
long long l=0,r=ps[n];
l=max(l,l1-ps[i]);
r=min(r,l2-ps[i]);
l=max(l,-r2+ps[i]);
r=min(r,-r1+ps[i]);
if(r>=l){
if((*st.rbegin())>=l){
auto x=st.lower_bound(l);
if(*x<=r){
return 1;
}
}
}
}
return 0;
}
long long find_shortcut(int n_, std::vector<int> l, std::vector<int> d,int c_)
{
n=n_;
c=c_;
alld[1]=d[0];
for(long long i=2;i<=n;i++){
all[i]=l[i-2];
ps[i]=all[i]+ps[i-1];
alld[i]=d[i-1];
}
long long low=-1,high=inf,mid;
while(high-low>1){
mid=(high+low)>>1;
if(check(mid)){
high=mid;
}else{
low=mid;
}
}
return high;
}
