#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#include "shortcut.h"
// #include "grader.cpp"
long long find_shortcut(int n, std::vector<int> _f, std::vector<int> _d, int _c)
{
ll c = _c;
vector<ll> f(n-1) , d(n);
for(int i=0;i<n-1;i++) f[i] = _f[i];
for(int i=0;i<n;i++) d[i] = _d[i];
ll ans = 1e18;
vector<ll> p(n);
for(int i=1;i<n;i++){
p[i] = p[i-1] + f[i-1];
}
vector<vector<ll>> f1(n,vector<ll>(n));
for(int j=0;j<n;j++){
f1[j][j] = d[j] - p[j];
for(int i=j+1;i<n;i++){
f1[j][i] = max(f1[j][i-1],d[i]-p[i]);
}
}
for(int r=0;r<n;r++){
for(int l=0;l<r;l++){
ll mx = 0;
vector<ll> f2(n) , f3(n);
f2[0] = -p[0] + d[0];
f3[l] = p[l] + d[l];
for(int i=1;i<n;i++) f2[i] = max(f2[i-1] , -p[i] + d[i]);
for(int i=l+1;i<n;i++) f3[i] = max(f3[i-1] , p[i] + d[i]);
for(int i=1;i<n;i++){
if(i <= l){
mx = max(mx , p[i] + d[i] + f1[0][i-1]);
}
else if(i <= r){
if(p[l] + p[r] + c < 2 * p[i] && l){
mx = max(mx , p[l] + f2[l-1] + c + p[r] - p[i] + d[i]);
}
else if(l){
mx = max(mx , p[i] + d[i] + f1[0][l-1]);
}
// for(int j=0;j<l;j++){
// ll x = min(p[i] - p[j] , p[l] - p[j] + c + p[r] - p[i]);
// mx = max(mx , x + d[i] + d[j]);
// }
ll C = -p[l] + c + p[r];
int idx = lower_bound(p.begin()+l,p.begin()+min(r,i),(2*p[i]-C+1)/2) - p.begin();
if(idx > l) {
mx = max(mx , f3[idx-1] + C - p[i] + d[i]);
}
if(idx < min(r,i)){
mx = max(mx , p[i] + d[i] + f1[idx][min(r,i)-1]);
}
// for(int j=l;j<min(r,i);j++){
// ll x = min(p[i] - p[j] , p[j] - p[l] + c + p[r] - p[i]);
// mx = max(mx , x + d[i] + d[j]);
// }
}
else {
if(l){
ll C = p[l] + c - p[r];
if(C >= 0) mx = max(mx , p[i] + d[i] + f1[0][l-1]);
else mx = max(mx , C + p[i] + d[i] + f2[l-1]);
}
// for(int j=0;j<l;j++){
// ll x = min(p[i] - p[j] , p[l] - p[j] + c + p[i] - p[r]);
// mx = max(mx , x + d[i] + d[j]);
// }
for(int j=l;j<min(r,i);j++){
ll x = min(p[i] - p[j] , p[j] - p[l] + c + p[i] - p[r]);
mx = max(mx , x + d[i] + d[j]);
}
mx = max(mx , p[i] + d[i] + f1[r][i-1]);
// for(int j=r;j<i;j++){
// mx = max(mx , p[i] - p[j] + d[i] + d[j]);
// }
}
}
ans = min(ans , mx);
}
}
return ans;
}
