#include "shortcut.h"
#include <bits/stdc++.h>
#define uwu return
using namespace std;
const int SIZE = 1e6 + 5;
const long long INF = 1e18 + 7;
long long pre[SIZE];
long long pre_max[SIZE], suf_max[SIZE];
vector <int> d;
long long calc_in(int l, int r, int c){
long long ret = 0;
for(int i = l; i <= r; i++){
for(int j = i; j <= r; j++){
ret = max(ret, min(pre[j] - pre[i], pre[r] - pre[j] + pre[i] - pre[l] + c) + d[i] + d[j]);
}
}
return ret;
}
long long calc_n(int l, int r){
long long ret = 0;
for(int i = l; i <= r; i++){
for(int j = i; j <= r; j++){
ret = max(ret, pre[j] - pre[i] + d[i] + d[j]);
}
}
return ret;
}
long long find_shortcut(int n, vector<int> l, vector<int> _d, int c){
n--;
d = _d;
for(int i = 1; i <= n; i++){
pre[i] = l[i] + pre[i - 1];
}
pre_max[0] = d[0];
for(int i = 1; i <= n; i++){
pre_max[i] = max(pre_max[i - 1], d[i] - pre[i]);
}
suf_max[n] = d[n] + pre[n];
for(int i = n - 1; i >= 0; i--){
suf_max[i] = max(suf_max[i + 1], d[i] + pre[i]);
}
long long now_ans = INF, ans = INF;
for(int l = 0, r = 0; l < n; l++){
while(r < n){
r++;
long long tmp = max({pre_max[l] + suf_max[r] + min(0LL, c - pre[r] + pre[l]), calc_in(l, r, c), calc_n(0, l), calc_n(r, n)});
if(tmp > now_ans){
r--;
break;
}
else
now_ans = tmp;
}
ans = min(now_ans, ans);
// cout << l << ' ' << r << ' ' << now_ans << '\n';
if(l < n)
now_ans = max({pre_max[l + 1] + suf_max[r] + min(0LL, c - pre[r] + pre[l + 1]), calc_in(l + 1, r, c), calc_n(0, l + 1), calc_n(r, n)});
}
uwu ans;
}
