#include <bits/stdc++.h>
#include "shortcut.h"
typedef long long int64;
using namespace std;
const int maxn = 3e3 + 2;
int64 pref[maxn];
struct way {
int64 l, r, cost;
};
long long find_shortcut(int n, vector<int> l, vector<int> d, int c){
vector <way> a;
for (int i = 0; i < n - 1; i++){
pref[i] = l[i] + (i ? pref[i-1]: 0);
}
auto query = [] (int l, int r) -> int64 {
if (l > r) swap(l, r);
if (r == 0 || l == r) return 0;
return pref[r-1] - (l - 1 == -1 ? 0: pref[l-1]);
};
for (int i = 0; i < n; i++){
for (int j = i + 1; j < n; j++){
a.push_back({i, j, d[i] + d[j] + query(i, j)});
}
}
sort(a.begin(), a.end(), [] (way &a, way &b) {
if (a.cost != b.cost) return a.cost > b.cost;
if (a.l != b.l) return a.l < b.l;
return a.r < b.r;
});
auto add = [&] (int l, int r) -> int64 {
int64 diam = 0;
for (int i = 0; i < n; i++){
for (int j = i + 1; j < n; j++){
diam = max(diam, (int64) d[i] + d[j] + min(query(i, j), query(i, l) + c + query(r, j)));
}
}
return diam;
};
int64 rs = 1e18;
for (int i = 0; i < min(10, n); i++){
rs = min(rs, add(a[i].l, a[i].r));
}
return rs;
}
