#include "shortcut.h"
#include<stdio.h>
#include<algorithm>
#define pll pair<long long, long long>
using namespace std;
int L[3010], C[3010], n, CCC;
long long Res, INF = 1e17, D[3010], P[3010], Deq[6010][2];
pll Do(int m){
int i, head = 0, tail = 0;
long long s = 0, ss;
for(i=0;i<m;i++)s += D[i];
ss = 0;
head = 1, tail = 0;
for(i=0;i<m;i++){
if(i!=m-1){
while(head <= tail && Deq[tail][1] >= ss-P[i])tail--;
tail++;
Deq[tail][0] = ss, Deq[tail][1] = ss-P[i];
}
ss += D[i];
}
long long MM = 0, MM2 = 0;
for(i=0;i<m-1;i++){
while(head <= tail && (ss - Deq[head][0])*2 > s)head++;
if(head <= tail){
MM = max(MM, ss + P[i] - Deq[head][1]);
}
while(head <= tail && Deq[tail][1] >= ss-P[i])tail--;
tail++;
Deq[tail][0] = ss, Deq[tail][1] = ss-P[i];
ss += D[i];
}
ss = 0;
for(i=0;i<m-1;i++){
long long t = s - D[m-1] - ss;
MM2 = max(MM2, min(t, s-t) + P[i] + P[m-1]);
ss += D[i];
}
return pll(MM,MM2);
}
pll Get(int b, int e){
long long MM = -1, s = 0, Mn = INF, rr = 0, rr2 = 0;
int i;
for(i=b;i>=0;i--){
rr = max(rr,s+C[i]-Mn);
MM = max(MM,s+C[i]);
Mn = min(Mn,s-C[i]);
if(i)s += L[i-1];
}
P[0]=MM;
D[0]=L[b];
for(i=b+1;i<e;i++){
P[i-b] = C[i];
D[i-b] = L[i];
}
MM = -1, s = 0, Mn = INF;
for(i=e;i<n;i++){
rr2 = max(rr2,s+C[i]-Mn);
MM = max(MM,s+C[i]);
Mn = min(Mn,s-C[i]);
if(i!=n-1)s += L[i];
}
P[e-b] = MM;
D[e-b] = CCC;
pll tp = Do(e-b+1);
rr2 = max(rr2, tp.second);
rr = max(rr, tp.first);
return pll(rr,rr2);
}
void Pro(int be){
int i, B, E, mid, rr = be;
B = be+1, E = n-1;
pll tp;
while(B<=E){
mid = (B+E)>>1;
tp = Get(be, mid);
if(tp.first <= tp.second){
rr = mid;
B = mid+1;
}
else{
E = mid-1;
}
}
if(rr != be){
tp = Get(be, rr);
Res = min(Res, max(tp.first,tp.second));
}
if(rr != n-1){
tp = Get(be,rr+1);
Res = min(Res, max(tp.first,tp.second));
}
}
long long find_shortcut(int N, std::vector<int> l, std::vector<int> d, int c)
{
n = N;
if(n>3000)return 0;
int i, j;
for(i=0;i<n-1;i++){
L[i] = l[i];
}
for(i=0;i<n;i++){
C[i] = d[i];
}
Res = INF;
CCC = c;
for(i=0;i<n;i++){
Pro(i);
}
return Res;
}
