#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++){
multiset<pair<ll,pair<ll,ll>>> s;
multiset<ll> s2;
ll z=0;
for(ll r=l+1; r<n; r++){
ll curr=0;
// A <-> A
ll prev=INF;
for(ll i=0; i<=l; i++){
curr=max(curr,a[i]-prev+d[i]);
prev=min(prev,a[i]-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--){
curr=max(curr,prev-a[i]+d[i]);
prev=max(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
while(!s.empty() && (*s.begin()).first<=a[r]){
s2.erase(s2.find((*s.begin()).second.first));
z=max(z,(*s.begin()).second.second);
s.erase(s.begin());
}
curr=max({curr,z,-*s2.begin()});
ll j=r;
for(ll i=l+1; i<r; i++){
if(a[j]-a[i]<=a[i]-a[l]+c+a[r]-a[j]) z=max(z,a[j]-a[i]+d[i]+d[j]);
else{
s2.insert(-(a[i]-a[l]+c-a[j]+d[i]+d[j]));
s.insert({-2*a[i]+a[l]-c+2*a[j],{-(a[i]-a[l]+c-a[j]+d[i]+d[j]),a[j]-a[i]+d[i]+d[j]}});
}
}
ans=min(ans,curr);
// cout<<l<<"-"<<r<<": "<<curr<<endl;
}
}
return ans;
}
