#include "shortcut.h"
#include <cstdio>
#include <cassert>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <limits.h>
#include <set>
#include <string>
#include <queue>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <deque>
#include <map>
#include <chrono>
#include <random>
#include <bitset>
#include <tuple>
#define SZ(x) int(x.size())
#define FR(i,a,b) for(int i=(a);i<(b);++i)
#define FOR(i,n) FR(i,0,n)
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define A first
#define B second
#define mp(a,b) make_pair(a,b)
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef unsigned __int128 U128;
typedef __int128 I128;
typedef std::pair<int,int> PII;
typedef std::pair<LL,LL> PLL;
using namespace std;
LL find_shortcut(int N, vector<int> l, vector<int> d, int c){
LL n=N;
vector<pair<PLL,LL> > adj[2*n+1];
FOR(i,n){
if (i<n-1) adj[i].push_back(mp(mp(i+1, l[i]),0));
if (i>0) adj[i].push_back(mp(mp(i-1, l[i-1]),0));
adj[i].push_back(mp(mp(i+n, d[i]),0));
adj[i+n].push_back(mp(mp(i, d[i]),0));
}
/*FOR(i,2*n+1){
cout<<i<<": ";
for (auto p:adj[i]) cout<<p.A.A<<" "<<p.A.B<<"\n";
}*/
LL ans=1e18;
FOR(i,n) FR(j,i+1,n){
adj[i].push_back(mp(mp(j,c),1));
adj[j].push_back(mp(mp(i,c),1));
LL tmp=0;
FOR(s,n){
LL dist[2*n+1];
memset(dist,-1,sizeof(dist));
priority_queue<PLL,vector<PLL>, greater<PLL> > pq;
pq.push(mp(0,s));
dist[s]=0;
while (!pq.empty()){
LL d=pq.top().A, u=pq.top().B;
pq.pop();
if (dist[u]!=d) continue;
for (pair<PLL,LL> p:adj[u]){
LL v=p.A.A, w=p.A.B;
if (dist[v]==-1 || dist[v]>d+w){
dist[v]=d+w;
pq.push(mp(dist[v],v));
}
}
}
LL mx=0;
FOR(i,2*n) mx=max(mx,dist[i]);
mx+=d[s];
tmp=max(tmp,mx);
}
ans=min(ans,tmp);
for (int it=SZ(adj[i])-1; it>=0; it--){
if (adj[i][it].B==1) adj[i].erase(adj[i].begin()+it);
}
for (int it=SZ(adj[j])-1; it>=0; it--){
if (adj[j][it].B==1) adj[j].erase(adj[j].begin()+it);
}
}
return ans;
}
