#include <bits/stdc++.h>
#define ll long long
#define sz(x) int(x.size())
#define fr first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
using namespace std;
const int MAXN = 2000001;
vector<pair<ll, ll>> grafo[MAXN];
ll N;
vector<int> D, L;
vector<ll> dijk(ll nod)
{
priority_queue<pair<ll, ll>> pq;
vector<ll> dist(N * 2 + 1, LLONG_MAX), proc(N * 2 + 1, 0);
pq.push({0, nod});
dist[nod] = 0;
while (pq.size())
{
nod = pq.top().se;
pq.pop();
if (proc[nod])
continue;
proc[nod] = 1;
for (auto k : grafo[nod])
{
if (dist[k.fr] > dist[nod] + k.se)
{
dist[k.fr] = dist[nod] + k.se;
pq.push({-dist[k.fr], k.fr});
}
}
}
return dist;
}
vector<ll> dis0;
ll calc(ll a, ll b)
{
ll i, n = N, ma = 0, j, act, dis;
vector<ll> disa = dijk(a), disb = dijk(b);
for (i = 0; i < n; i++)
{
ma = max(ma, 1ll * D[i]);
for (j = i + 1; j < n; j++)
{
dis = abs(dis0[i] - dis0[j]);
dis = min(disa[i] + disa[j], dis);
dis = min(dis, disb[i] + disb[j]);
dis = dis + D[i] + D[j];
ma = max(dis, ma);
}
}
return ma;
}
long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c)
{
N = n;
ll i, j, mi = LLONG_MAX;
D = d;
L = l;
for (i = 0; i < sz(l); i++)
{
grafo[i].pb({i + 1, l[i]});
grafo[i + 1].pb({i, l[i]});
}
for (i = 0; i < n; i++)
{
if (d[i] > 0)
{
grafo[i].pb({i + n, d[i]});
grafo[i + n].pb({i, d[i]});
}
}
dis0 = dijk(0);
for (i = 0; i < n; i++)
{
for (j = i + 1; j < n; j++)
{
grafo[i].pb({j, c});
grafo[j].pb({i, c});
mi = min(mi, calc(i, j));
grafo[i].pop_back();
grafo[j].pop_back();
}
}
return mi;
}
