#include "shortcut.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
using vi = vector<int>;
using ll = long long;
ll find_shortcut(int n, vi l, vi d, int c) {
vector<ll> sl;
for(int i = 0; i < n - 1; ++i) {
sl.push_back(l[i]);
if(i) sl[i] += sl[i - 1];
}
auto dist_direct = [&](int u, int v) {
if(u > v) swap(u, v);
if(!v) return 0ll;
if(u) return sl[v - 1] - sl[ u - 1 ];
else return sl[v - 1];
};
vector<vector<ll> > DD(n, vector(n, 0ll));
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j) DD[i][j] = dist_direct(i, j);
auto dist = [&](int u, int v, int st, int dr) { /// (st, dr) express line
ll re = DD[u][v];
re = min(re, DD[u][st] + DD[dr][v] + c);
// re = min(re, DD[u][dr] + DD[st][v] + c);
return re + d[u] + d[v];
};
ll re = 1e18;
auto simu = [&](int st, int dr, ll rec) {
ll cre = 0, ri, rj;
for(int i = 0; i < n; ++i)
for(int j = i + 1; j < n; ++j) {
ll val = dist(i, j, st, dr);
if(val > cre) {
ri = i;
rj = j;
cre = val;
}
if(cre > rec) return cre;
}
return cre;
};
vector<pair<int, int> > O;
for(int st = 0; st < n; ++st) {
for(int dr = st + 1; dr < n; ++dr) {
O.push_back({st, dr});
}
}
mt19937 rng(1);
shuffle(O.begin(), O.end(), rng);
for(auto [st, dr] : O) {
auto cre = simu(st, dr, re);
re = min(re, cre);
}
return re;
}
