# include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
typedef std::vector<int> V;
typedef long long ll;
const int N = 510;
ll dist[N][N],pf[N],lt[N],rt[N],ans=0ll,C,cur,suf[N],pref[N];
int n;
long long find_shortcut (int n, V l, V d, int c) {
pf[0]=0; C=ll(c);
for (int i=1;i<n;i++) pf[i]=pf[i-1]+ll(l[i-1]);
for (int i=0;i<n;i++)
for (int j=0;j<n;j++){
dist[i][j]=ll(d[i])+ll(d[j])+pf[max(i,j)]-pf[min(i,j)];
if (i==j) dist[i][j]-=ll(d[i]);
if (j>=i) rt[i]=max(rt[i],dist[i][j]);
if (j<=i) lt[i]=max(lt[i],dist[i][j]);
ans=max(ans,dist[i][j]);
}
pref[0]=lt[0];
for (int i=1;i<n;i++) pref[i]=max(pref[i-1],lt[i]);
suf[n-1]=rt[n-1];
for (int i=n-2;i>=0;i--) suf[i]=max(suf[i+1],rt[i]);
for (int Lt=0;Lt<n;Lt++)
for (int r=Lt+1;r<n;r++){
cur=max(lt[Lt]-ll(d[Lt]),ll(d[Lt]))+min(C,pf[r]-pf[Lt])+max(rt[r]-ll(d[r]),ll(d[r]));
cur=max(cur,suf[r]);
cur=max(cur,pref[Lt]);
for (int L=Lt;L<=r;L++){
cur=max(cur,min(lt[L],ll(d[L])+C+(pf[r]-pf[L])+max(lt[Lt]-ll(d[Lt]),ll(d[Lt]))));
cur=max(cur,min(rt[L],ll(d[L])+C+(pf[L]-pf[Lt])+max(rt[r]-ll(d[r]),ll(d[r]))));
for (int R=L+1;R<=r;R++){
cur=max(cur,min(dist[L][R],ll(d[L])+ll(d[R])+(pf[L]-pf[Lt])+(pf[r]-pf[R])+C));
}
}
ans=min(ans,cur);
}
return ans;
}
