#include "shortcut.h"
#include <iostream>
#include <assert.h>
const int N = 1e6+2;
typedef long long ll;
using namespace std;
ll dp1[N],dp2[N];
ll dp3[N],dp4[N];
ll sums[N];
long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c)
{
for(int i=0;i<n;i++) {
if(i==0) dp1[i]=d[i];
else dp1[i]=max((ll)d[i],dp1[i-1]+l[i-1]);
}
for(int i=n-1;i>=0;i--) {
if(i==n-1) dp2[i]=d[i];
else dp2[i]=max((ll)d[i],dp2[i+1]+l[i]);
}
for(int i=0;i<n;i++) {
if(i==0) dp3[i]=d[i];
else dp3[i]=max(dp3[i-1],d[i]+l[i-1]+dp1[i-1]);
}
for(int i=n-1;i>=0;i--) {
if(i==n-1) dp4[i]=d[i];
else dp4[i]=max(dp4[i+1],l[i]+dp2[i+1]+d[i]);
}
for(int i=1;i<n;i++) {
sums[i]=l[i-1]+sums[i-1];
}
// for(int i=0;i<n;i++) {
// cout<<i<<" : "<<dp3[i]<<" , "<<dp4[i]<<endl;
// }
ll ans=dp3[n-1];
ll lx;
ll prev=0;bool Gf=0,Gf2=0;
for(int i=0;i<n;i++) {
prev=0,Gf=0,Gf2=0;
for(int j=i+1;j<n;j++) {
lx=sums[j]-sums[i];
if(lx<=c) continue;
ll f=max(dp3[i],max(dp4[j],c+dp1[i]+dp2[j]));
for(int x=i+1;x<j;x++) {
ll _x=sums[x]-sums[i];
f=max(f,min(_x,lx-_x+c)+dp1[i]+d[x]);
f=max(f,min(lx-_x,_x+c)+dp2[j]+d[x]);
for(int y=x+1;y<j;y++) {
ll f2=sums[y]-sums[x];
f=max(f,min(f2,lx+c-f2)+d[x]+d[y]);
}
}
if(Gf==0) {
Gf=1;
prev=f;
}
else {
if(Gf2==0) {
if(f>prev) {
Gf2=1;
}
}
else {
assert(f>=prev);
}
}
// cout<<i<<" , "<<j<<" : "<<f<<endl;
ans=min(ans,f);
}
}
return ans;
}
