#include "shortcut.h"
#define ll long long
#include <bits/stdc++.h>
using namespace std;
const int MOD=1000000007;
#define x first
const ll LLINF=1ll<<60;
#define y second
#define pb push_back
#define pii pair<int,int>
#define vi vector<int>
#define vl vector<ll>
const char en='\n';
void fil(int start,vl&dist,int n,vi l,vi d,int c,int lo,int hi)
{
priority_queue<pair<ll,int>> pq;
pq.push({0,start});
vector<bool> bio;
bio.resize(2*n);
while (pq.size())
{
int i=pq.top().y;
ll di=pq.top().x;
pq.pop();
if (bio[i]) continue;
bio[i]=1;
dist[i]=-di;
//cout<<lo<<' '<<hi<<' '<<i<<' '<<start<<' '<<-di<<endl;
if (i%2==0)
{
pq.push({di-d[i/2],i+1});
if (i<n*2-2) pq.push({di-l[i/2],i+2});
if (i/2==lo) pq.push({di-c,hi*2});
if (i>0) pq.push({di-l[i/2-1],i-2});
if (i/2==hi) pq.push({di-c,lo*2});
}
else
{
pq.push({di-d[i/2],i-1});
}
}
}
const int dissss=-361;
ll find_shortcut(int n,vi l,vi d,int c)
{
assert(n<=10);
ll mi=LLINF;
for (int lll=0;lll<n;++lll) for (int r=lll+1;r<n;++r)
{
ll ma=0,ii=-1,jj=-1;
for (int j=0;j<n;++j)
{
vl dist(2*n,LLINF);
fil(j*2+1,dist,n,l,d,c,lll,r);
for (int i=0;i<2*n;++i)
{
ma=max(ma,dist[i]);
if (dist[i]==dissss) ii=i,jj=j*2+1;
}
}
mi=min(mi,ma);
if (ma==dissss) cout<<lll<<' '<<r<<' '<<ii<<' '<<jj<<en;
}
return mi;
}
