#include "shortcut.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>
bool assign_min(T& a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template<typename T>
bool assign_max(T& a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
/*
9 30
10 10 10 10 10 10 10 10
20 0 30 0 0 40 0 40 0
*/
int n;
vector<vector<pair<int, int>>> g;
vector<ll> dist;
int get_far(int u) {
vector<int> vis(2 * n + 1);
dist.assign(2 * n + 1, 1e18);
priority_queue<pair<ll, ll>> pq;
pq.push({0, u});
dist[u] = 0;
while (!pq.empty()) {
int u = pq.top().second;
pq.pop();
if (vis[u]) continue;
vis[u] = 1;
for (auto [v, c] : g[u]) {
if (dist[u] + c < dist[v]) {
dist[v] = dist[u] + c;
pq.push({-dist[v], v});
}
}
}
int best = u;
for (int i = 1; i <= 2 * n; i++) {
if (dist[i] != 1e18 && dist[i] > dist[best]) {
best = i;
}
}
return best;
}
ll solve(vector<array<ll, 3>> edges, bool print = 0) {
g.assign(2 * n + 1, {});
for (auto [a, b, c] : edges) {
g[a].push_back({b, c});
g[b].push_back({a, c});
}
ll ans = 0;
for (int u = 1; u <= 2 * n; ++u) {
int v = get_far(u);
ans = max(ans, dist[v]);
}
return ans;
}
ll find_shortcut(int N, vector<int> l, vector<int> d, int c) {
n = N;
vector<array<ll, 3>> edges;
for (int i = 1; i <= n; i++) {
if (d[i - 1] != 0) {
edges.push_back({i, n + i, d[i - 1]});
}
if (i < n) {
edges.push_back({i, i + 1, l[i - 1]});
}
}
ll ans = solve(edges);
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
edges.push_back({i, j, c});
ans = min(ans, solve(edges, (i == 1 && j == 7)));
edges.pop_back();
}
}
return ans;
}
