#include <bits/stdc++.h>
#ifndef ARTHUR_LOCAL
#include "shortcut.h"
#endif
using namespace std;
using ll = long long;
void merger(pair<int,int> &a, pair<int,int> b)
{
// cout << a.first << " " << a.second << endl;
int from = max(a.first,b.first);
int to = min(a.second,b.second);
if(from>=to) a = {-1,-1};
else a = make_pair(from,to);
}
ll find_shortcut(int n, vector<int> L, vector<int> D, int c)
{
vector<ll> pref_sums(n+1);
for(int i=1; i<n; i++)
{
pref_sums[i]=pref_sums[i-1]+ll(L[i-1]);
}
ll ans = 1e18;
for(int i=0; i<n; i++)
{
for(int j=i+1; j<n; j++)
{
// shortcut is between i and j
ll cur_ans = 0;
for(int a=0; a<n; a++)
{
for(int b=a+1; b<n; b++)
{
ll cur = ll(D[a]+D[b]);
ll useb = pref_sums[max(b,j)]-pref_sums[min(b,j)];
useb += ll(c);
useb += pref_sums[max(a,i)]-pref_sums[min(a,i)];
cur += min(useb,pref_sums[b]-pref_sums[a]);
cur_ans=max(cur_ans,cur);
}
}
// cout << i << " " << j << " " << cur_ans << endl;
ans=min(ans,cur_ans);
}
}
return ans;
}
#ifdef ARTHUR_LOCAL
int main()
{
cout << find_shortcut(4, {10,10,10}, {10,10,10,10}, 1) << endl;
}
#endif
