#pragma GCC optimize("O3,unroll-loops,Ofast")
#include "shortcut.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long
int INF = numeric_limits<int>::max()/2;
int calc(int a, int b, int32_t n, vector<int>& pn, vector<int>& sn, std::vector<int32_t>& d, int32_t c){
int ma = 0;
// LL
for(int i = 0; i <= a; i++){
for(int j = i+1; j <= a; j++){
ma = max(ma, pn[j]-pn[i]+d[i]+d[j]);
}
}
// MM
for(int i = a; i <=b; i++){
for(int j = i+1; j <= b; j++){
ma = max(ma, min(pn[j]-pn[i],pn[i]-pn[a]+sn[j]-sn[b]+c)+d[i]+d[j]);
}
}
// RR
for(int i = b; i <=n-1; i++){
for(int j = i+1; j <= n-1; j++){
ma = max(ma, pn[j]-pn[i]+d[i]+d[j]);
}
}
// LR
for(int i = 0; i <=a; i++){
for(int j = b; j <= n-1; j++){
ma = max(ma, pn[a]-pn[i]+sn[b]-sn[j]+d[i]+d[j]+c);
}
}
// LM
for(int i = 0; i <=a; i++){
for(int j = max(a,i+1); j <= b; j++){
ma = max(ma, pn[a]-pn[i]+d[i]+min(sn[j]-sn[b]+c,pn[j]-pn[a])+d[j]);
}
}
// MR
for(int i = a; i <=b; i++){
for(int j = max(b,i+1); j <= n-1; j++){
ma = max(ma, sn[b]-sn[j]+d[i]+min(sn[i]-sn[b],pn[i]-pn[a]+c)+d[j]);
}
}
return ma;
}
long long find_shortcut(int32_t n, std::vector<int32_t> l, std::vector<int32_t> d, int32_t c)
{
vector<int> pref(n);
for(int i = 1; i < n; i++){
pref[i] = pref[i-1]+l[i-1];
}
vector<int> suff(n);
for(int i = n-2; i >= 0; i--){
suff[i] = suff[i+1]+l[i];
}
int mi = calc(0,1,n,pref,suff,d,l[0]);
for(int a = 0; a < n; a++){
for(int b = a+1; b < n; b++){
int v = calc(a,b,n,pref,suff,d,c);
mi = min(mi,v);
}
}
return mi;
}
