#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e18;
long long find_shortcut(int n, vector<int> x, vector<int> d, int c){
ll a[n]={};
for(ll i=1; i<n; i++){
a[i]=a[i-1]+x[i-1];
}
ll ans=INF;
for(ll l=0; l<n; l++){
for(ll r=l+1; r<n; r++){
ll curr=0;
// A <-> A
ll prev=INF;
for(ll i=0; i<=l; i++){
prev=min(prev,a[i]-d[i]);
curr=max(curr,a[i]-prev+d[i]);
}
// A <-> C
for(ll i=r; i<n; i++){
curr=max(curr,a[i]-prev+d[i]-max(0ll,a[r]-a[l]-c));
}
// A <-> B
for(ll i=l+1; i<r; i++){
curr=max(curr,min(a[i],a[r]-a[i]+c+a[l])-prev+d[i]);
}
// C <-> C
prev=-INF;
for(ll i=n-1; i>=r; i--){
prev=max(prev,a[i]+d[i]);
curr=max(curr,prev-a[i]+d[i]);
}
// B <-> C
for(ll i=l+1; i<r; i++){
curr=max(curr,prev+min(-a[i],-a[r]+a[i]-a[l]+c)+d[i]);
}
// B <-> B
for(ll i=l+1; i<r; i++){
for(ll j=i+1; j<r; j++){
curr=max(curr,min(a[j]-a[i],a[i]-a[l]+c+a[r]-a[j])+d[i]+d[j]);
}
}
ans=min(ans,curr);
// cout<<l<<"-"<<r<<": "<<curr<<endl;
}
}
return ans;
}
