#include "shortcut.h"
#include <iostream>
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;
for(int i=0;i<n;i++) {
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]);
}
}
ans=min(ans,f);
// if(sums[j]-sums[i]<=c) continue;
// if(f==0) {
// //first time this runs for a particular i(starting).
// }
// f=1;
// cout<<i<<" "<<j<<" "<<ans<<endl;
}
}
return ans;
}
