//#include "shortcut.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<vector<pair<int,ll>>> cad;
ll a, b, c;
pair<ll,ll> asd(int d)
{
cad[a].push_back({b,c});
cad[b].push_back({a,c});
priority_queue<pair<ll,ll>> q;
vector<ll> v(cad.size()+1,-1);
q.push({0,d});
pair<ll,ll> asd={0,0};
while(!q.empty())
{
pair<ll,ll> temp=q.top();q.pop();
if(v[temp.second]==-1)
{
v[temp.second]=-temp.first;
asd=max(asd,{v[temp.second],temp.second});
for(auto i:cad[temp.second])
{
if(v[i.first]==-1)
q.push({temp.first-i.second,i.first});
}
}
}
cad[a].pop_back();
cad[b].pop_back();
return asd;
}
long long find_shortcut(int n, vector<int> l, vector<int> d, int C)
{
cad.resize(2*n+5);
for(int i=0; i<n-1; i++)
{
cad[i].push_back({i+1,l[i]});
cad[i+1].push_back({i,l[i]});
cad[i].push_back({n+i,d[i]});
cad[n+i].push_back({i,d[i]});
}
cad[n-1].push_back({n-1+n,d[n-1]});
cad[n-1+n].push_back({n-1,d[n-1]});
ll ans=1e17;
c=C;
for(int i=0; i<n; i++)
{
for(int j=i+1; j<n; j++)
{
a=i;b=j;
pair<ll,ll> temp=asd(0);
pair<ll,ll> t1=asd(temp.second);
temp=max(temp,t1);
t1=asd(n-1);
temp=max(temp,asd(t1.second));
ans=min(ans,temp.first);
}
}
return ans;
}
