#include <vector>
#include <set>
using namespace std;
int const N=1e6+10;
multiset<pair<int,int>>nei[N]={};
long long dis[N]={};
long long ans=1e17+10;
int ns;
long long bfs(int x)
{
for (int i=0;i<ns;i++)
dis[i]=1e17+10;
dis[x]=0;
set<pair<int,int>>s;
s.insert({0,x});
while (s.size())
{
int x=(*begin(s)).second;
s.erase(*begin(s));
for (auto i:nei[x])
{
if (dis[i.first]>dis[x]+i.second)
{
s.erase({dis[i.first],i.first});
dis[i.first]=dis[x]+i.second;
s.insert({dis[i.first],i.first});
}
}
}
long long z=0;
for (int i=0;i<ns;i++)
z=max(z,dis[i]);
return z;
}
void find()
{
long long f=0;
for (int i=0;i<ns;i++)
{
long long z=bfs(i);
f=max(f,z);
}
ans=min(ans,f);
}
long long find_shortcut(int n,vector<int>l,vector<int>d,int c)
{
for (int i=0;i<n-1;i++)
{
nei[i].insert({i+1,l[i]});
nei[i+1].insert({i,l[i]});
}
ns=n;
for (int i=0;i<n;i++)
{
if (d[i])
{
nei[i].insert({ns,d[i]});
nei[ns].insert({i,d[i]});
ns++;
}
}
for (int i=0;i<n;i++)
for (int j=i+1;j<n;j++)
{
nei[i].insert({j,c});
nei[j].insert({i,c});
find();
nei[i].erase(nei[i].find({j,c}));
nei[j].erase(nei[j].find({i,c}));
}
return ans;
}
