//#include "shortcut.h"
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <cstdint>
#include <cassert>
#include <bitset>
#include <random>
#include <chrono>
#include <cstring>
#define shit short int
#define ll long long
#define ld long double
//#define int ll
#define For(i, n) for(int i = 0; i < (int)n; i++)
#define ffor(i, a, n) for(int i = (int)a; i < (int)n; i++)
#define rfor(i, n) for(int i = (int)n; i >= (int)0; i--)
#define rffor(i, a, n) for(int i = (int)n; i >= (int)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<ll, ll>
#define pld pair<ld, ld>
#define NEK 2000000000000000
#define mod 1000000007
#define mod2 1000000009
#define rsz resize
#define prv 43
#define prv2 47
#define D 8
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define all(x) (x).begin(), (x).end()
#define sig 0.0000001
using namespace std;
bool check(ll mid, vec<ll>& d, vec<ll>& ps, ll c) {
int n = d.size();
ll pp = (-2) * NEK, pm = (-2) * NEK, mp = (-2) * NEK, mm = (-2) * NEK;
For(i, n) {
ffor(j, i + 1, n) {
if (ps[j] - ps[i] + d[i] + d[j] <= mid) continue;
ll mojko = mid - d[i] - d[j] - c;
//(ps[i] - y) + (ps[j] - z) <= mojko
//ps[i] + ps[j] - mojko <= y+z
pp = max(pp, ps[i] + ps[j] - mojko);
//ps[i] - ps[j] - mojko <= y - z
pm = max(pm, ps[i] - ps[j] - mojko);
//ps[j] - ps[i] - mojko <= z - y
mp = max(mp, ps[j] - ps[i] - mojko);
//-ps[i] - ps[j] - mojko <= - z - y
mm = max(mm, -ps[i] - ps[j] - mojko);
}
}
For(i, n) {
ffor(j, i + 1, n) {
if (ps[i] + ps[j] >= pp && ps[i] - ps[j] >= pm && ps[j] - ps[i] >= mp && -ps[i] - ps[j] >= mm) {
return 1;
}
}
}
return 0;
}
ll find_shortcut(int n1, vec<int> len, vec<int> d1, int c1) {
ll n = n1;
ll c = c1;
vec<ll> d;
For(i, d1.size()) d.push_back(d1[i]);
vec<ll> ps(n);
ps[0] = 0;
For(i, (n - 1)) {
ps[i + 1] = ps[i] + len[i];
}
ll l = 0, r = NEK;
while (l < r) {
ll mid = (l + r) / 2;
if (check(mid, d, ps, c)) r = mid;
else l = mid + 1;
}
return l;
}
/*
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, c;
while (1) {
//cin >> n >> c;
n = 10;
c = rand() % 10;
vec<int> l(n - 1), d(n);
For(i, (n - 1)) {
//cin >> l[i];
l[i] = rand() % 10;
}
For(i, n) {
//cin >> d[i];
d[i] = rand() % 10;
}
ll odp1 = find_shortcut_pomale(n, l, d, c);
ll odp2 = find_shortcut(n, l, d, c);
if (odp1 != odp2) {
odp1 = find_shortcut_pomale(n, l, d, c);
odp2 = find_shortcut(n, l, d, c);
}
cout << odp2 << '\n';
//return 0;
}
return 0;
}*/
