#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;
// cout<<x1<<" "<<x2<<" "<<y1<<" wtf "<<y2<<endl;
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]);
}
}
}
for(long long i=1;i<=n;i++){
for(long long j=i;j<=n;j++){
if(dakh(ps[j],ps[i])){
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;
}
