// ~ Be Name Khoda ~ //
#include "shortcut.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define fi first
#define se second
const int maxn = 1e6 + 10;
const int maxn5 = 3e3 + 10;
const int maxnt = 1.2e6 + 10;
const int maxn3 = 1e3 + 10;
const int mod = 1e9 + 7;
const int lg = 20;
const ll inf = 1e18;
int n;
ll c;
vector <ll> d;
ll ps[maxn5], ps2[maxn5];
set <pair<ll, int>> av;
vector <pair<int, ll>> adj[maxn5];
ll dis(int a, int b){
if(a > b)
swap(a, b);
return ps[b] - ps[a];
}
long long find_shortcut(int N, std::vector<int> l, std::vector<int> D, int C)
{
n = N;
c = C;
for(auto u : D)
d.pb(u);
ps[0] = 0;
for(int i = 1; i < n; i++)
ps[i] = ps[i - 1] + l[i - 1];
ll mn = inf;
for(int i = 0; i < n; i++) for(int j = 0; j < n; j++){
ll mx = 0;
for(int x = 0; x < n; x++) for(int y = x + 1; y < n; y++){
mx = max(mx, d[x] + d[y] + min({dis(x, y), dis(x, i) + c + dis(y, j), dis(x, j) + c + dis(y, i)}));
//cout << i << ' ' << j << ' ' << x << ' ' << y << ' ' << dis(x, y) << ' ' << dis(x, i) + c + dis(y, j) << ' ' << dis(x, j) + c + dis(y, i) << endl;
}
mn = min(mn, mx);
//cout << i << ' ' << j << ' ' << mn << endl;
}
return mn;
}
