#include "shortcut.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> pii;
typedef vector<pii> vii;
typedef vector<vii> vvii;
const ll INF=100000000000000000;
void dfs(int n,vvii conex, int v, ll &mej){
vector<bool> porvisitar(2*n,true);
priority_queue<pii> cola;
cola.push(pii{0,v});
int recurs=0;
while (cola.size()){
if (recurs>3000) break;
pii x=cola.top();
cola.pop();
if (porvisitar[x.second]){
porvisitar[x.second]=false;
mej=max(mej,-x.first);
for (pii y:conex[x.second]){
if (porvisitar[y.second]) cola.push(pii{x.first-y.first,y.second});
}
}
recurs++;
}
}
ll find_shortcut(int n, vi l, vi d, int c)
{
vvii conexiones(2*n);
for (int i=0;i<n-1;i++){
conexiones[i].push_back(pii{l[i],i+1});
conexiones[i+1].push_back(pii{l[i],i});
}
for (int i=0;i<n;i++){
conexiones[i].push_back(pii{d[i],i+n});
conexiones[n+i].push_back(pii{d[i],i});
}
ll mejor=INF;
for (int i=0;i<n;i++){
for (int j=i+1;j<n;j++){
vvii conex=conexiones;
conex[i].push_back(pii{c,j});
conex[j].push_back(pii({c,i}));
ll mej=0;
for (int v=n;v<2*n;v++){
dfs(n,conex,v,mej);
}
mejor=min(mejor,mej);
}
}
return mejor;
}
