#include "shortcut.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pill pair<ll, ll>
#define mp make_pair
#define f first
#define s second
using namespace std;
const ll N = 3e5;
int n, c;
ll le[N];
ll d[N];
ll pr[N];
ll precPr[N];
ll precSuf[N];
struct seg {
ll t[4 * N] = {0};
ll p[4 * N] = {0};
void push(ll v, ll tl, ll tr) {
t[v] = t[v] + p[v];
if(tl < tr) {
p[v * 2] += p[v];
p[v * 2 + 1] += p[v];
}
p[v] = 0;
}
void upd(ll p, ll z, ll v = 1, ll tl = 0, ll tr = n) {
push(v, tl, tr);
if(tl == tr) {
t[v] = z;
return;
}
ll m = (tl + tr) >> 1ll;
if(p <= m) {
upd(p, z, v * 2, tl, m);
push(v * 2 + 1, m + 1, tr);
} else {
upd(p, z, v * 2 + 1, m + 1, tr);
push(v * 2, tl, m);
}
t[v] = max(t[v * 2], t[v * 2 + 1]);
}
void dob(ll l, ll r, ll z, ll v = 1, ll tl = 0, ll tr = n) {
push(v, tl, tr);
if(l > tr || tl > r)return;
if(l <= tl && tr <= r) {
p[v] += z;
push(v, tl, tr);
return;
}
ll m = (tl + tr) >> 1ll;
dob(l, r, z, v * 2, tl, m);
dob(l, r, z, v * 2 + 1, m + 1, tr);
t[v] = max(t[v * 2], t[v * 2 + 1]);
}
ll get(ll l, ll r, ll v = 1, ll tl = 0, ll tr = n) {
push(v, tl, tr);
if(l > tr || tl > r)return 0;
if(l <= tl && tr <= r)return t[v];
ll m = (tl + tr) >> 1ll;
return max(get(l, r, v * 2, tl, m), get(l, r, v * 2 + 1, m + 1, tr));
}
} rt[3];
ll calc(ll l, ll r) {
ll sub = 0;
for(int i = 0; i < n; i++)
sub = max(sub, d[i]);
for(int i = 0; i < l; i++) {
for(int j = i + 1; j < l; j++) {
sub = max(sub, pr[j] - pr[i] + d[i] + d[j]);
}
}
for(int i = r; i < n; i++) {
for(int j = i + 1; j < n; j++) {
sub = max(sub, pr[j] - pr[i] + d[i] + d[j]);
}
}
for(int i = 0; i < l; i++) {
for(int j = r + 1; j < n; j++) {
sub = max(sub, d[i] + d[j] + pr[l] - pr[i] + pr[j] - pr[r] + min((ll)c, pr[r] - pr[l]));
}
}
for(int i = 0; i < l; i++) {
for(int j = l; j <= r; j++) {
ll dist = (pr[l] - pr[i]) + min(c + pr[r] - pr[j], pr[j] - pr[l]) + d[i] + d[j];
sub = max(sub, dist);
}
}
for(int j = l; j <= r; j++) {
for(int i = r + 1; i < n; i++) {
ll dist = (pr[i] - pr[r]) + min(c + pr[j] - pr[l], pr[r] - pr[j]) + d[i] + d[j];
sub = max(sub, dist);
}
}
for(int i = l; i < r; i++) {
for(int j = i + 1; j <= r; j++) {
ll dist = min(pr[j] - pr[i], pr[i] - pr[l] + pr[r] - pr[j] + c) + d[i] + d[j];
sub = max(sub, dist);
}
}
return sub;
}
ll find_shortcut(int na, vector<int> l, vector<int> di, int C) {
c = C;
n = na;
for(int i = 0; i < n - 1; i++) {
le[i + 1] = l[i];
}
pr[0] = 0;
for(int i = 1; i < n; i++)
pr[i] = pr[i - 1] + le[i];
for(int i = 0; i < n; i++)
d[i] = di[i];
for(int i = 0; i < n; i++) {
rt[0].upd(i, pr[i] - d[i]);
rt[1].upd(i, pr[i] + d[i]);
}
ll ans = calc(0, 1);
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
ans = min(ans, calc(i, j));
}
}
return ans;
}
