#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
typedef long long ll;
const int MAXN = 1e6;
ll pfAll[MAXN], sfAll[MAXN], pos[MAXN];
int pfSrc[MAXN], sfSrc[MAXN];
ll dist[MAXN];
vector<pair<int, ll>> adj[MAXN];
int N;
void Dijkstra(int src) {
for (int i=0; i<N; i++) dist[i] = 1e18;
dist[src] = 0;
priority_queue<
pair<ll, int>,
vector<pair<ll, int>>,
greater<pair<ll, int>>
> pq; pq.push({0, src});
while (!pq.empty()) {
auto [d, v] = pq.top(); pq.pop();
if (d > dist[v]) continue;
for (auto [viz, w] : adj[v]) {
// cout << v << "->" << viz << endl;
// cout << dist[viz] << ' ' << d << ' ' << w << endl;
if (dist[viz] > d + w) {
// cout << "ok" << endl;
dist[viz] = d + w;
pq.push({dist[viz], viz});
}
}
}
}
ll find_shortcut(int n, vector<int> l, vector<int> d, int c) {
for (int i=0; i<n-1; i++) {
adj[i].emplace_back(i+1, l[i]);
adj[i+1].emplace_back(i, l[i]);
}
for (int i=0; i<n; i++) {
adj[i].emplace_back(n+i, d[i]);
adj[n+i].emplace_back(i, d[i]);
}
N = 2*n;
ll res = 1e18;
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
adj[i].emplace_back(j, c);
adj[j].emplace_back(i, c);
Dijkstra(0);
int p1 = 0;
for (int k=0; k<N; k++) {
if (dist[k] > dist[p1]) p1 = k;
}
Dijkstra(p1);
ll tmp = 0;
for (int k=0; k<N; k++) {
tmp = max(tmp, dist[k]);
}
res = min(res, tmp);
adj[i].pop_back(); adj[j].pop_back();
}
}
return res;
// pfAll[0] = d[0]; pfSrc[0] = 0;
// for (int i=0; i<n-1; i++) {
// pfAll[i+1] = max((ll)d[i+1], pfAll[i] + l[i]);
// pfSrc[i+1] = (d[i+1] > pfAll[i] + l[i] ? i+1 : pfSrc[i]);
// }
// sfAll[n-1] = d[n-1]; sfSrc[n-1] = n-1;
// for (int i=n-2; i>=0; i--) {
// sfAll[i] = max((ll)d[i], sfAll[i+1] + l[i]);
// sfSrc[i] = (d[i] > sfAll[i+1] + l[i] ? i : sfSrc[i+1]);
// }
// int ans = 0;
// for (int i=0; i<n; i++) {
// ans = (pfAll[i] + sfAll[i] > pfAll[ans] + sfAll[ans] ? i : ans);
// }
// vector<ll> diam; bool left = true, right = true;
// if (d[pfSrc[ans]] > 0) {
// left = false;
// diam.push_back(d[pfSrc[ans]]);
// }
// for (int i=pfSrc[ans]; i<sfSrc[ans]; i++) {
// diam.push_back(l[i]);
// }
// if (d[sfSrc[ans]] > 0) {
// diam.push_back(d[sfSrc[ans]]);
// right = false;
// }
// N = n = (int)diam.size() + 1;
// for (int i=0; i<n-1; i++) {
// adj[i].emplace_back(i+1, diam[i]);
// adj[i+1].emplace_back(i, diam[i]);
// }
// // pos[0] = 0;
// // for (int i=1; i<n; i++) pos[i] = pos[i-1] + diam[i-1];
// ll res = 1e18;
// for (int i=(!left); i<n; i++) {
// for (int j=i; j<n-(!right); j++) {
// adj[i].emplace_back(j, c);
// adj[j].emplace_back(i, c);
// Dijkstra(0);
// int p1 = 0;
// for (int i=0; i<n; i++) {
// if (dist[i] > dist[p1]) i = p1;
// }
// Dijkstra(p1);
// ll tmp = 0;
// for (int i=0; i<n; i++) {
// tmp = max(tmp, dist[i]);
// }
// if (tmp < res) {
// cout << tmp << ' ' << i << ' ' << j << endl;
// }
// res = min(res, tmp);
// adj[i].pop_back(); adj[j].pop_back();
// }
// }
// return res;
// for (int i=0; i<n; i++) cout << pos[i] << ' ';
// cout << endl;
// ll lAns = c, rAns = pos[n-1], res = pos[n-1];
// while (lAns <= rAns) {
// ll mid = (lAns + rAns) / 2;
// cout << lAns << ' ' << rAns << ':' << mid << endl;
// bool check = false; int k = 0;
// for (int i=0; i<n; i++) {
// if (pos[i] < mid) k = i;
// }
// cout << k << endl;
// if (k == n-1) check = true;
// for (int i=0+(!left), j=0; i<=k and !check; i++) {
// bool stop = false;
// while (!stop and pos[i] + c + pos[n-1] - pos[j] > mid) {
// if (j == n-1-(!right)) stop = true;
// j++;
// }
// if (stop) break;
// if (pos[i] + c + max(pos[j] - pos[k], pos[n-1]-pos[j]) <= mid) {
// cout << i << ' ' << j << endl;
// check = true;
// }
// }
// if (check) {
// res = mid;
// rAns = mid-1;
// } else lAns = mid+1;
// }
// return res;
}
