#include <bits/stdc++.h>
#include "shortcut.h"
using namespace std;
const int MAX_N = 6005;
const long long INF = 1e18 + 7;
int n;
multiset <pair <int, int>> graph[MAX_N];
long long dist[MAX_N][MAX_N];
bool visited[MAX_N];
void bfs(int s) {
for (int i = 0; i < 2 * n; i++) {
dist[s][i] = INF;
visited[i] = false;
}
priority_queue <pair <long long, int>> pq;
pq.emplace(0, s);
dist[s][s] = 0;
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (visited[u] == true) continue;
visited[u] = true;
for (auto [v, w] : graph[u]) {
if (visited[v] == false and dist[s][u] + w < dist[s][v]) {
dist[s][v] = dist[s][u] + w;
pq.emplace(-dist[s][v], v);
}
}
}
}
long long find_shortcut(int n, vector <int> l, vector <int> d, int c) {
::n = n;
for (int i = 0; i < n - 1; i++) {
graph[i].emplace(i + 1, l[i]);
graph[i + 1].emplace(i, l[i]);
}
for (int i = 0; i < n; i++) {
graph[i].emplace(n + i, d[i]);
graph[n + i].emplace(i, d[i]);
}
long long ans = INF;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
graph[i].emplace(j, c);
graph[j].emplace(i, c);
for (int i = 0; i < 2 * n; i++) bfs(i);
long long max_dist = 0;
for (int i = 0; i < 2 * n; i++) {
for (int j = 0; j < 2 * n; j++) max_dist = max(max_dist, dist[i][j]);
}
ans = min(ans, max_dist);
graph[i].erase(graph[i].lower_bound(make_pair(j, c)));
graph[j].erase(graph[j].lower_bound(make_pair(i, c)));
}
}
return ans;
}
