#include "shortcut.h"
#include<bits/stdc++.h>
using namespace std;
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ll long long
#define fall(i,a,b) for(int i=a;i<=b;i++)
#define rfall(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
const ll inf=1e16;
typedef pair<ll,ll> pii;
long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c){
vector<ll> pref(n),suf(n),dist(n),rdist(n),adicionou(n);
pref[0]=d[0];
fall(i,1,n-1) pref[i]=max(1ll*d[i],pref[i-1]+1ll*l[i-1]);
suf[n-1]=d[n-1];
rfall(i,n-2,0) suf[i]=max(suf[i+1]+1ll*l[i],d[i]*1ll);
dist[0]=d[0];
fall(i,1,n-1) dist[i]=max(dist[i-1],pref[i-1]+1ll*l[i-1]+1ll*d[i]);
rdist[n-1]=d[n-1];
rfall(i,n-2,0) rdist[i]=max(rdist[i],suf[i+1]+1ll*l[i]+1ll*d[i]);
auto calc=[&](int a,int r){
ll gap=0,dr=d[r],dl=d[a];
fall(i,a,r-1) gap+=l[i];
ll p=r,dc=0,cur=0,mx=0;
multiset<ll> st; st.insert(d[r]); adicionou[r]=d[r];
//cout<<r<<" "<<adicionou[r]<<"\n";
rfall(i,r-1,a){ //acha o par mais distante entre as bordas da bridge
cur+=l[i];
dc-=l[i];
while(p>i){
ll x=adicionou[p]+cur;
if(2*x>gap+c+2*d[p]){
st.erase(st.find(adicionou[p]));
dc=max(dc,gap-x+c+2*d[p]);
p--;
}
else break;
}
ll x=adicionou[r]+cur;
dr=max(dr,d[i]+min(cur,c+gap-cur));
if(i==a) dl=max(dl,dc);
if(i==a && !st.empty()) dl=max(dl,*st.rbegin()+cur);
mx=max(mx,dc+d[i]);
if(!st.empty()) mx=max(mx,*st.rbegin()+cur+d[i]);
st.insert(d[i]-cur);
adicionou[i]=d[i]-cur;
}
if(a) mx=max(mx,dist[a-1]);
if(r!=n-1) mx=max(mx,rdist[r+1]);
gap=min(gap,1ll*c);
int d1=0,d2=0;
if(a) d1=pref[a-1]+l[a-1];
if(r!=n-1) d2=suf[r+1]+l[r];
mx=max({mx,d1+dl,d2+dr,d1+gap+d2});
return mx;
};
ll ans=inf;
fall(i,0,n-1)
fall(j,i+1,n-1){
ans=min(ans,calc(i,j));
//if(calc(i,j)==100) cout<<i<<" "<<j<<"\n";
}
return ans;
}
