#include <cstdio>
#include <cassert>
#include "shortcut.h"
#pragma once
#include <vector>
#include <bits/stdc++.h>
using namespace std;
struct node{
long long x,y,d;
};
long long find_shortcut(int n, std::vector <int> ll, std::vector <int> d, int c){
vector<long long>pref_max(n,0);
vector<long long>suff_max(n,0);
for (int i = 0 ;i<n;++i){
if (i == 0){
pref_max[i] = d[i];
}
else{
pref_max[i] = max((long long)d[i],pref_max[i - 1] + ll[i - 1]);
}
}
for (int i = n - 1;i>=0;--i){
if (i == n - 1){
suff_max[i] = d[i];
}
else{
suff_max[i] = max((long long)d[i],suff_max[i + 1] + ll[i]);
}
}
vector<long long>pref_seg(n,0);
vector<long long>suff_seg(n,0);
for (int i = 0;i<n;++i){
if (i == 0){
pref_seg[i] = d[i];
}
else{
pref_seg[i] = max(pref_seg[i - 1],pref_max[i - 1] + ll[i - 1] + d[i]);
}
}
for (int i = n - 1;i>=0;--i){
if (i == n - 1){
suff_seg[i] = d[i];
}
else{
suff_seg[i] = max(suff_seg[i + 1],suff_max[i + 1] + ll[i] + d[i]);
}
}
vector<long long>pref(n,0);
for (int i = 0;i<n - 1;++i){
pref[i + 1] = pref[i] + ll[i];
}
auto query = [&](int l,int r){
if (l > r){
swap(l,r);
}
return pref[r] - pref[l];
};
long long v = query(0,1);
for (int i = 0;i<n - 1;++i){
v = max(v,pref_max[i] + suff_max[i + 1] + ll[i]);
}
auto check = [&](long long mid){
vector<node>pos;
for (int i = 0;i<n;++i){
for (int j = i + 1;j<n;++j){
if (d[i] + d[j] + query(i,j) > mid){
pos.push_back({i,j,mid - d[i] - d[j] - c});
}
}
}
sort(pos.begin(),pos.end(),[&](auto x,auto y){
if (x.d == y.d)return x.y < y.y;
return x.d < y.d;
});
for (int i = 0;i<n;++i){
bool valid = true;
for (int j = i + 1;j<n;++j){
bool ok = true;
for (auto x:pos){
if (query(i,x.x) + query(j,x.y) <= x.d || query(i,x.y) + query(j,x.x) <= x.d){
continue;
}
ok = false;
if (x.y <= j){
valid = false;
}
break;
}
if (ok){
return 1;
}
if (!valid)break;
}
}
return 0;
};
long long pos = 0;
long long left = 0,right = 1e12;
while(left<=right){
long long mid = (left + right)>>1;
if (check(mid)){
right = mid - 1;
pos = mid;
}
else{
left = mid + 1;
}
}
return pos;
}
