#include "shortcut.h"
//Challenge: Accepted
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r){
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 100005
#define pii pair<int, int>
#define ff first
#define ss second
const ll inf = 1LL<<60;
long long find_shortcut(int n, vector<int> L, vector<int> D, int C) {
vector<ll> pref(n, 0), suf(n, 0), pma(n, 0), sma(n, 0), cy(n, 0);
for (int i = 0;i < n-1;i++) cy[i+1] = cy[i] + L[i];
for (int i = 0;i < n;i++) {
pref[i] = D[i];
pma[i] = D[i];
if (i) {
pma[i] = max(pma[i] + pref[i-1] + L[i-1], pma[i-1]);
pref[i] = max(pref[i], pref[i-1] + L[i-1]);
}
}
for (int i = n - 1;i >= 0;i--) {
suf[i] = D[i];
sma[i] = D[i];
if (i < n - 1) {
sma[i] = max(sma[i] + suf[i+1] + L[i], sma[i+1]);
suf[i] = max(suf[i], suf[i+1] + L[i]);
}
}
vector<ll> wei(2*n, 0), p(2*n, 0);
ll ans = inf;
for (int a = 0;a < n;a ++) {
for (int b = a+1;b < n;b++) {
ll val = max(pma[a], sma[b]);
int siz = b - a + 1;
ll tot = cy[b] - cy[a] + C;
for (int i = a;i <= b;i++) {
if (i == a) wei[i-a] = wei[i-a+siz] = pref[a];
else if (i == b) wei[i-a] = wei[i-a+siz] = suf[b];
else wei[i-a] = wei[i-a + siz] = D[i];
}
for (int i = 0;i < siz;i++) {
p[i] = cy[i+a] - cy[a];
p[i+siz] = p[i] + tot;
}
deque<int> deq;
for (int i = 0;i < 2 * siz;i++) {
while (deq.size() && (p[i] - p[deq.front()])*2 > tot) deq.pop_front();
if (deq.size()) val = max(val, wei[i] + wei[deq.front()] + p[i] - p[deq.front()]);
while (deq.size() && wei[i] - p[i] >= wei[deq.back()] - p[deq.back()]) deq.pop_back();
deq.push_back(i);
}
debug(a, b, val);
ans = min(ans, val);
}
}
return ans;
}
