#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1e6+5;
ll liga[MAXN], v[MAXN];
ll dp[MAXN], rdp[MAXN];
ll aux[MAXN], raux[MAXN];
ll d[MAXN];
ll respf;
int n, x;
ll testa(int a, int b, ll tam) {
ll val=0; if(b<a) swap(a, b);
for(int i=a; i<=b; i++) {
for(int j=i+1; j<=b; j++) {
ll aa=min(d[j]-d[i], tam-d[j]+d[i]);
aa+= (i==a) ? aux[i] : v[i];
aa+= (j==b) ? raux[j] : v[j];
val=max(val, aa);
// printf(" %d %d // %d %d %lld >> %lld\n", i, j, a, b, tam, val);
}
}
return val;
}
ll find_shortcut(int N, vector<int> lll, vector<int> ddd, int X)
{
n=N; x=X;
for(int i=2; i<=n; i++) liga[i]=lll[i-2];
for(int i=1; i<=n; i++) v[i]=ddd[i-1];
for(int i=1; i<=n; i++) {
d[i]=d[i-1]+liga[i];
dp[i]=max(dp[i-1], aux[i-1]+liga[i]+v[i]);
aux[i]=max(aux[i-1]+liga[i], v[i]);
}
for(int i=n; i>=1; i--) {
rdp[i]=max(rdp[i+1], raux[i+1]+liga[i+1]+v[i]);
raux[i]=max(raux[i+1]+liga[i+1], v[i]);
}
respf=max(dp[n], rdp[1]);
for(int a=1; a<=n; a++) {
for(int b=a+1; b<=n; b++) {
ll tam=d[b]-d[a]+x;
ll val=max(dp[a], rdp[b]);
val=max(val, testa(a, b, tam));
// printf("testa %d %d >> %lld // dp[a e b] >> %lld %lld + %lld >> val= %lld\n", a, b, tam, dp[a], rdp[b], min(d[b]-d[a], tam-d[b]+d[a]), val);
respf=min(respf, val);
}
}
return respf;
}
