#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;
});
// for (auto i: a){
// cout << i.l << " " << i.r << " " << i.cost << "\n";
// }
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;
};
auto check = [&] (int64 x) -> bool {
int64 mxl = 0, mnr = 0;
for (int i = 0; i < a.size(); i++){
if (a[i].cost <= x) break;
mxl = max(mxl, a[i].l);
mnr = max(mnr, a[i].r);
}
// cout << mxl << " " << mnr << " " << x << "\n";
if (mnr == 1e9) return 1;
if (mxl > mnr) return 0;
return add(mxl, mnr) <= x;
};
int64 il = 0, ir = 1e15, rs = -1;
while (il <= ir) {
int64 mid = (il + ir) / 2;
if (check(mid)) {
rs = mid;
ir = mid - 1;
}
else {
il = mid + 1;
}
}
// int64 rs = 1e18;
// for (int i = 0; i < n; i++){
// for (int j = i + 1; j < n; j++){
// // cout << i << " " << j << " " << add(i,j) << "\n";
// rs = min(rs, add(i, j));
// }
// }
return rs;
}
