#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<int> ps,D,segl[2],segr[2];
void build(int id,int l,int r){
if(l==r){
segl[0][id]=segr[0][id]=0;
segl[1][id]=segr[1][id]=D[l];
return;
}
int m=l+(r-l)/2;
build(id*2,l,m);
build(id*2+1,m+1,r);
segl[0][id]=max(segl[0][id*2],segl[1][id*2+1]+ps[m+1]-ps[l]);
segr[0][id]=max(segr[0][id*2+1],segr[1][id*2]+ps[r]-ps[m]);
segl[1][id]=max(segl[1][id*2],segl[1][id*2+1]+ps[m+1]-ps[l]);
segr[1][id]=max(segr[1][id*2+1],segr[1][id*2]+ps[r]-ps[m]);
}
void init(int n){
segl[0].resize(4*n);
segr[1].resize(4*n);
segl[1].resize(4*n);
segr[0].resize(4*n);
build(1,1,n);
}
int queryl(int id,int l,int r,int L,int R){
if(l>R||r<L){
return 0;
}else if(l>=L&&r<=R){
return ps[l]-ps[L]+segl[l!=L][id];
}
int m=l+(r-l)/2;
return max(queryl(id*2,l,m,L,R),queryl(id*2+1,m+1,r,L,R));
}
int queryr(int id,int l,int r,int L,int R){
if(l>R||r<L){
return 0;
}else if(l>=L&&r<=R){
return ps[R]-ps[r]+segr[r!=R][id];
}
int m=l+(r-l)/2;
return max(queryr(id*2,l,m,L,R),queryr(id*2+1,m+1,r,L,R));
}
vector<pair<int,int>> edges[209];
int check(int n){
int ans=0;
vector<int> dist(2*n+9,1e15);
priority_queue<pair<int,int>> pq;
for(int i=1;i<=2*n;i++){
fill(dist.begin(),dist.end(),1e15);
dist[i]=0;
pq.push({0,i});
while(!pq.empty()){
int u=pq.top().second,w=-pq.top().first;
pq.pop();
if(dist[u]!=w){
continue;
}
for(int j=0;j<edges[u].size();j++){
if(dist[edges[u][j].first]>w+edges[u][j].second){
dist[edges[u][j].first]=w+edges[u][j].second;
pq.push({-dist[edges[u][j].first],edges[u][j].first});
}
}
}
for(int j=1;j<=2*n;j++){
ans=max(ans,dist[j]);
}
}
return ans;
}
long long find_shortcut(int32_t n, std::vector<int32_t> l, std::vector<int32_t> d, int32_t c)
{
if(n>100){
return 0;
}
for(int i=0;i<n-1;i++){
edges[i+1].push_back({i+2,l[i]});
edges[i+2].push_back({i+1,l[i]});
}
for(int i=0;i<n;i++){
edges[i+1].push_back({n+i+1,d[i]});
edges[n+i+1].push_back({i+1,d[i]});
}
int ans=check(n);
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
edges[i].push_back({j,c});
edges[j].push_back({i,c});
ans=min(ans,check(n));
edges[i].pop_back();
edges[j].pop_back();
}
}
return ans;
// vector<int> pre, suf;
// pre.resize(n+1,0);suf.resize(n+1,0);ps.resize(n+1,0);D.resize(n+1,0);
// pre[1]=d[0];suf[n]=d[n-1];
// for(int i=0;i<n-1;i++){
// pre[i+2]=max(pre[i+1]+l[i],(long long)d[i+1]);
// ps[i+2]=ps[i+1]+l[i];
// }
// for(int i=n-2;i>=0;i--){
// suf[i+1]=max(suf[i+2]+l[i],(long long)d[i]);
// }
// int tmp=0,L=1,R=1,cur;
// for(int i=0;i<n-1;i++){
// tmp=max(tmp,pre[i+1]+l[i]+suf[i+2]);
// }
// for(int i=0;i<n;i++){
// D[i+1]=d[i];
// }
// init(n);
// cur=tmp;
// pair<int,int> pt={1,1},ma={0,0},ptnew,manew;
// while(R<n){
// // cout << L << ' ' << R << ' ' << pt.first << ' ' << pt.second << ' ' << ma.first << ' ' << ma.second << ' ' << cur << '\n';
// R++;
// ptnew=pt;
// while(ps[ptnew.first+1]-ps[L]+c<=ps[R]-ps[ptnew.first+1]){
// ptnew.first++;
// }
// while(ps[R]-ps[ptnew.second]+c>ps[ptnew.second]-ps[L]&&ptnew.second<R){
// ptnew.second++;
// }
// manew={max(queryl(1,1,n,L,ptnew.first),pre[L]),max(queryr(1,1,n,ptnew.second,R),suf[R])};
// // cout << L << ' ' << R << ' ' << ptnew.first << ' ' << ptnew.second << ' ' << manew.first << ' ' << manew.second << ' ' << cur << '\n';
// // cout << max(max(manew.first+c,queryr(1,1,n,ptnew.first+1,R))+suf[R],max(manew.second+c,queryl(1,1,n,L,ptnew.second-1))+pre[L]) << '\n';
// if(max(max(manew.first+c,queryr(1,1,n,ptnew.first+1,R))+suf[R],max(manew.second+c,queryl(1,1,n,L,ptnew.second-1))+pre[L])<cur||L==R-1){
// pt=ptnew;
// ma=manew;
// cur=max(max(manew.first+c,queryr(1,1,n,ptnew.first+1,R))+suf[R],max(manew.second+c,queryl(1,1,n,L,ptnew.second-1))+pre[L]);
// tmp=min(tmp,cur);
// continue;
// }
// R--;
// L++;
// ptnew=pt;
// while(ps[ptnew.first+1]-ps[L]+c<=ps[R]-ps[ptnew.first+1]){
// ptnew.first++;
// }
// while(ps[R]-ps[ptnew.second]+c>ps[ptnew.second]-ps[L]&&ptnew.second<R){
// ptnew.second++;
// }
// manew={max(queryl(1,1,n,L,ptnew.first),pre[L]),max(queryr(1,1,n,ptnew.second,R),suf[R])};
// // cout << L << ' ' << R << ' ' << ptnew.first << ' ' << ptnew.second << ' ' << manew.first << ' ' << manew.second << ' ' << cur << '\n';
// // cout << max(max(manew.first+c,queryr(1,1,n,ptnew.first+1,R))+suf[R],max(manew.second+c,queryl(1,1,n,L,ptnew.second-1))+pre[L]) << '\n';
// pt=ptnew;
// ma=manew;
// cur=max(max(manew.first+c,queryr(1,1,n,ptnew.first+1,R))+suf[R],max(manew.second+c,queryl(1,1,n,L,ptnew.second-1))+pre[L]);
// tmp=min(tmp,cur);
// }
// return tmp;
}
