#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;
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);
}
vec<vec<int>> rq;
bool chck(int mn) {
for (int u = 1; u <= n; u++)
if (ext[u] > mn) return false;
rq.clear();
for (int u = 1; u <= n; u++) {
vec<int> fr;
for (int v = 1; v <= n; v++)
if (v != u && dst[u][v] + ext[u] + ext[v] > mn) fr.push_back(v);
if (fr.empty()) continue;
if (fr[0] < u && fr.back() > u) return false;
if (fr.back() < u) {
int v = fr.back();
rq.push_back({v, u, dst[u][v] + ext[u] + ext[v] - mn});
} else {
int v = fr[0];
rq.push_back({u, v, dst[u][v] + ext[u] + ext[v] - mn});
}
}
// for (vec<int> x : rq) cerr << x[0] << " " << x[1] << " " << x[2] << '\n';
int l = 1, r = n, x = 0;
for (vec<int> y : rq)
l = max(l, y[0]), r = min(r, y[1]), x = max(x, y[2]);
// cerr << mn << ": " << l << " " << r << " " << x << '\n';
if (l > r) return false;
int sv = max(dst[l][r] - d, 0ll);
return (sv >= x);
}
int srch() {
int lw = 1, hg = 1e18;
while (lw != hg) {
int md = (lw + hg) / 2;
if (chck(md)) hg = md;
else lw = md + 1;
}
return lw;
}
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 srch();
}
