#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define arr array
#define vec vector
#define pii pair<int, int>
#define fir first
#define sec second
const int N = 3e2 + 5, INF = 1e18;
int n, d;
arr<int, N> ext;
arr<vec<pii>, N> adj;
arr<arr<int, N>, N> dst;
void dfs(int u, int src, int pr = 0) {
for (pii x : adj[u])
if (x.fir != pr) dst[src][x.fir] = dst[src][u] + x.sec, dfs(x.fir, src, u);
}
void dst_cmp() {
for (int u = 1; u <= n; u++)
dfs(u, u);
}
int dmtr_cmp() {
int ans = INF;
for (int a = 1; a <= n; a++) {
for (int b = a + 1; b <= n; b++) {
int dmtr = 0;
for (int u = 1; u <= n; u++) {
dmtr = max(dmtr, ext[u]);
for (int v = u + 1; v <= n; v++) {
int sp = min({ext[u] + dst[u][v] + ext[v],
ext[u] + dst[u][a] + d + dst[b][v] + ext[v],
ext[u] + dst[u][b] + d + dst[a][v] + ext[v]});
dmtr = max(dmtr, sp);
}
}
ans = min(ans, dmtr);
}
}
return ans;
}
int find_shortcut(signed _n, vec<signed> _edg, vec<signed> _ext, signed _d) {
n = _n, d = _d;
for (int u = 1; u < n; u++)
adj[u].push_back({u + 1, _edg[u - 1]}), adj[u + 1].push_back({u, _edg[u - 1]});
for (int u = 1; u <= n; u++) ext[u] = _ext[u - 1];
dst_cmp();
return dmtr_cmp();
}
