#include "shortcut.h"
#include <vector>
#include <queue>
#include <utility>
#include <iostream>
#include <limits.h>
#include <algorithm>
using namespace std;
#define v vector
#define pii pair<int,int>
#define fi first
#define se second
#define pq priority_queue
long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c)
{
v<v<long long>> adj(n,v<long long>(n, LLONG_MAX));
for(int i=0;i<n-1;i++){
adj[i][i+1] = l[i];
adj[i+1][i] = l[i];
adj[i][i]=0;
}
adj[n-1][n-1]=0;
for(int i=0;i<n-1;i++){
for(int j=i+2;j<n;j++){
adj[i][j] = adj[i][j-1]+adj[j-1][j];
adj[j][i] = adj[i][j];
}
}
long long out=0;
v<v<long long>> large;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
long long dist=adj[i][j]+d[i]+d[j];
if(dist>out) out=dist;
large.push_back({-dist, i, j});
}
}
sort(large.begin(),large.end());
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
long long diam=0;
for(v<long long> it: large){
long long a=it[1];
long long b=it[2];
long long dist= -it[0];
long long dist2= d[a] + adj[a][i] + adj[b][j] + d[b] +c;
long long dist3= d[a] + adj[a][j] + adj[b][i] + d[b] +c;
if(dist2<dist) dist=dist2;
if(dist3<dist) dist=dist3;
if(dist>diam) diam=dist;
if(diam>out) break;
}
if(diam<out) out=diam;
}
}
return out;
}
