#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
// #include "shortcut_c.h"
#include <cstdio>
using namespace std;
#define ll long long
const int N = 6e3 + 10;
const ll inf = 1e16;
long long maxLeft[N], maxRight[N], kox[N];
long long maxLeftDiam[N], maxRightDiam[N];
multiset<pair<ll, long long>> adj[N];
int ni;
pair<long long, long long> djik(int node) {
vector<bool> used(ni + 1);
vector<long long> dist(ni + 1, inf);
priority_queue<pair<ll, ll>, vector<pair<ll, ll>> , greater<pair<ll, ll>> > q;
dist[node] = 0;
q.push({0, node});
while(!q.empty()) {
auto u = q.top();
q.pop();
if(used[u.second]) {
continue;
}
used[u.second] = true;
for(auto i: adj[u.second]) {
if(dist[i.first] > dist[u.second] + i.second) {
dist[i.first] = dist[u.second] + i.second;
q.push({dist[i.first], i.first});
}
}
}
pair<ll, ll> answ = {-1, -1};
for(int i = 0; i < ni; i++) {
if(dist[i] == inf) {
assert(false);
}
if(dist[i] > answ.first) {
answ = {dist[i], i};
}
}
return answ;
}
long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c) {
maxLeft[0] = d[0];
for(int i = 1; i < n; i++) {
maxLeft[i] = max(maxLeft[i - 1] + (long long)l[i - 1], (long long)d[i]);
}
maxRight[n - 1] = d[n - 1];
for(int i = n - 2; i >= 0; i--) {
maxRight[i] = max(maxRight[i + 1] + (long long)l[i], (long long)d[i]);
}
maxLeftDiam[0] = maxLeft[0];
for(int i = 1; i < n; i++) {
maxLeftDiam[i] = max(maxLeftDiam[i - 1], maxLeft[i - 1] + (long long)l[i - 1] + (long long)d[i]);
}
maxRightDiam[n - 1] = maxRight[n - 1];
for(int i = n - 2; i >= 0; i--) {
maxRightDiam[i] = max(maxRightDiam[i + 1], maxRight[i + 1] + (long long)l[i] + (long long)d[i]);
}
ni = n;
if(d[0]) {
kox[0] = ni;
adj[0].insert({ni, d[0]});
adj[ni++].insert({0, d[0]});
}
for(int i = 1; i < n; i++) {
adj[i - 1].insert({i, l[i - 1]});
adj[i].insert({i - 1, l[i - 1]});
if(d[i]) {
kox[i] = ni;
adj[i].insert({ni, d[i]});
adj[ni++].insert({i, d[i]});
}
}
long long minDiametr = djik(djik(0).second).first;
for(int i = 0; i < n; i++) {
long long s = 0;
for(int j = i + 1; j < n; j++) {
s += l[j - 1];
if(s <= c) {
continue;
}
adj[i].insert({j, (long long)c});
adj[j].insert({i, (long long)c});
long long maxi = max({maxLeftDiam[i], maxRightDiam[j], maxLeft[i] + maxRight[j] + c});
// cout << maxi << endl;
for(int k = i; k <= j; k++) {
if(kox[k]) {
maxi = max(maxi, djik(kox[k]).first);
} else {
maxi = max(maxi, djik(k).first);
}
}
// cout << i << " " << j << endl;
// cout << maxi << endl;
minDiametr = min(maxi, minDiametr);
adj[i].erase(adj[i].find(make_pair(j, (ll)c)));
adj[j].erase(adj[j].find(make_pair(i, (ll)c)));
}
}
return minDiametr;
}
