#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#include "shortcut.h"
int c;
ll d[3000];
ll pref[3000];
pair<ll,bool> pr;
int n;
inline ll query(int l, int r){
if (l==r) return 0ll;
if (r<l) swap(l,r);
return pref[r]-pref[l];
}
inline void dene(int l, int r){
ll leftside=0;
ll rightside=0;
int indi = 0;
deque<pair<ll,int>> hoaydaaa;
ll bruh=-1;
for (int i = 0; i < n; i++){
if (i){
while (indi<i){
if (query(indi,l)+query(i,r)+c<=query(indi,i)){
bruh=max(bruh,query(indi,l)+d[indi]);
indi++;
}
else break;
}
ll crr = 0;
while (hoaydaaa.size()>0){
ll node = hoaydaaa.back().second;
if (indi>node){
hoaydaaa.pop_back();
}
else break;
}
if (hoaydaaa.size()>0){
crr=max(crr,d[i]+pref[i]+hoaydaaa.back().first);
}
if (bruh!=-1){
crr=max(crr,d[i]+bruh+c+query(i,r));
}
if (i>=r){
rightside=max(rightside,crr);
}
else {
leftside=max(leftside,crr);
}
}
while (hoaydaaa.size() && hoaydaaa.front().first<=d[i]-pref[i]){
hoaydaaa.pop_front();
}
hoaydaaa.push_front({d[i]-pref[i],i});
}
pr={max(leftside,rightside),(rightside>leftside)};
};
long long find_shortcut(int _n, std::vector<int> _p, std::vector<int> _d, int _c)
{
n=_n;
c=_c;
pref[0]=0;
for (int i = 0; i < n-1; i++){
pref[i+1]=_p[i]+pref[i];
}
for (int i = 0; i < n; ++i)
{
d[i]=_d[i];
}
ll ans = LONG_LONG_MAX;
for (int l = 0; l < n; l++){
int ll = l, rr = n-1;
while (ll<rr){
int mid = ll+(rr-ll)/2;
dene(l,mid);
ans=min(ans,pr.first);
if (!pr.second){
rr=mid;
}
else {
ll=mid+1;
}
}
dene(l,ll);
ans=min(ans,pr.first);
}
for (int i = 0; i < n; ++i)
{
ans=max(ans,d[i]);
}
return ans;
}
