#include "shortcut.h"
#include<vector>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define int long long
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define f first
#define s second
const int minf=-1e18,inf=1e18;
long long find_shortcut(int32_t n, std::vector<int32_t> l, std::vector<int32_t> d, int32_t c){
vector<int>pref(n);
vector<pii>pmx(n+1,{0,0}),smx(n+1,{0,0});
vector<pii>pmx2(n+1,{0,0}),smx2(n+1,{0,0});
for(int i=1;i<n;i++)pref[i]=l[i-1]+pref[i-1];
pmx[0]={0,-1};
smx[n-1]={0,-1};
for(int i=0;i<n-1;i++){
pmx[i+1]=max(pmx[i],{d[i]-pref[i],i});
}
for(int i=n-1;i>0;i--){
smx[i-1]=max(smx[i],{d[i]+pref[i],i});
}
auto getdist=[&](int a,int b){
if(a>b)swap(a,b);
return pref[b]-pref[a];
};
auto get=[&](int a,int b,int i,int j){
return min(getdist(a,i)+getdist(b,j),getdist(a,j)+getdist(b,i));
};
auto getrd=[&](int a,int b,int i,int j){
if(a<0||b<0)return minf;
return min(getdist(a,b),c+get(a,b,i,j))+d[a]+d[b]*(!(a==b));
};
int ans=inf;
for(int i=0;i<n-1;i++)for(int j=i+1;j<n;j++){
int dia=minf;
for(int k=0;k<n;k++){
dia=max(dia,getrd(k,i,i,j));
dia=max(dia,getrd(k,j,i,j));
dia=max(dia,getrd(k,pmx[k].s,i,j));
dia=max(dia,getrd(k,smx[k].s,i,j));
}
for(int k=i;k<=j;k++){
pmx2[k]={d[k]+pref[k],k};
if(k!=i)pmx2[k]=max(pmx2[k],pmx2[k-1]);
}
for(int k=j;k>=i;k--){
smx2[k]={d[k]-pref[k],k};
if(k!=j)smx2[k]=max(smx2[k],smx2[k+1]);
}
for(int k=0;k<=j;k++){
int l=max(i,k),r=j,pos=n-1;
while(l<=r){
int mid=l+(r-l)/2;
if(c+getdist(k,i)+getdist(mid,j)<getdist(k,mid))r=mid-1,pos=min(pos,mid);
else l=mid+1;
}
dia=max(dia,getrd(k,smx2[pos].s,i,j));
if(pos)dia=max(dia,getrd(k,pmx2[pos-1].s,i,j));
}
for(int k=j+1;k<n;k++){
int l=i,r=min(j,k),pos=0;
while(l<=r){
int mid=l+(r-l)/2;
if(c+get(k,mid,i,j)<getdist(k,mid))l=mid+1,pos=max(pos,mid);
else r=mid-1;
}
dia=max(dia,getrd(k,pmx2[pos].s,i,j));
if(pos)dia=max(dia,getrd(k,smx2[pos-1].s,i,j));
}
dia=max(dia,getrd(pmx[i+1].s,smx[j-1].s,i,j));
ans=min(ans,dia);
}
return ans;
}
