#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;
class intervalac {
ll n;
vec<ll> l, r, in;
public:
intervalac(ll vel) {
n = 1;
while (n < vel) n *= 2;
l.resize(2 * n); r.resize(2 * n); in.resize(2 * n, (-1) * NEK);
For(i, n) {
l[i + n] = r[i + n] = i;
}
rffor(i, 1, (n - 1)) {
l[i] = l[i * 2];
r[i] = r[i * 2 + 1];
}
return;
}
void zmen(ll a, ll b) {
a += n;
in[a] = b;
a /= 2;
while (a) {
in[a] = max(in[a * 2], in[a * 2 + 1]);
a /= 2;
}
return;
}
ll daj(ll a, ll b, ll s = 1) {
if (l[s] > b || r[s] < a) return (-1) * NEK;
if (a <= l[s] && r[s] <= b) return in[s];
return max(daj(a, b, s * 2), daj(a, b, s * 2 + 1));
}
};
bool check1(vec<ll>&d, vec<ll>&ps, ll k, ll mid, ll x, ll y, ll c) {
ll n = d.size();
ll priamo = (ps[mid] - ps[k]);
ll otocka = (ps[k] - ps[x]) + (ps[y] - ps[mid]) + c;
return priamo <= otocka;
}
bool check2(vec<ll>& d, vec<ll >& ps, ll k, ll mid, ll x, ll y, ll c) {
ll n = d.size();
ll priamo = (ps[k] - ps[mid]);
ll otocka = (ps[y] - ps[k]) + (ps[mid] - ps[x]) + c;
return priamo <= otocka;
}
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];
}
vec<ll> mpref(n), msuf(n);
ll mojo = d[0] - ps[0];
mpref[0] = d[0];
ffor(i, 1, n) {
mpref[i] = mojo + ps[i] + d[i];
mpref[i] = max(mpref[i], d[i]);
mpref[i] = max(mpref[i], mpref[i - 1]);
mojo = max(mojo, d[i] - ps[i]);
}
mojo = ps.back() + d.back();
msuf[n - 1] = d[n - 1];
rfor(i, (n - 2)) {
msuf[i] = mojo - ps[i] + d[i];
msuf[i] = max(msuf[i], d[i]);
msuf[i] = max(msuf[i], msuf[i + 1]);
mojo = max(mojo, d[i] + ps[i]);
}
vec<vec<ll>> s1(n, vec<ll>(n)), s2(n, vec<ll>(n));
For(i, n) {
ll maxi1 = d[i] - ps[i], maxi2 = d[i] + ps[i];
for (int j = i; j <= n; j++) {
maxi1 = max(maxi1, d[j] - ps[j]);
maxi2 = max(maxi2, d[j] + ps[j]);
s1[i][j] = maxi1;
s2[i][j] = maxi2;
}
}
ll lv = 0;
ll rv = NEK;
while (lv < rv) {
ll mid = (lv + rv) / 2;
//tuto skontrolujeme
//ak je spravne tak
bool ok = 0;
For(x, n) {
ll sy = x;
ll pos = n-1;
for (ll y = n - 1; y > x; y--) {
pos = min(pos, y - 1);
ll lavo = s1[0][x] + ps[x];
ll pravo = s2[y][n] - ps[y];
ll maxi = pravo + lavo + min(ps[y] - ps[x], c);
maxi = max(maxi, mpref[x]);
maxi = max(maxi, msuf[y]);
while (pos >= x) {
ll priamo = ps[y] - ps[pos];
ll otocka = ps[pos] - ps[x] + c;
if (priamo > otocka) break;
maxi = max(maxi, ps[y] - ps[pos] + d[pos] + pravo);
pos--;
}
maxi = max(maxi, s2[x][pos] - ps[x] + c + pravo);
if (maxi > mid) {
sy = y;
break;
}
}
ll y = sy + 1;
if (y == n) continue;
ll lavo = s1[0][x] + ps[x];
ll pravo = s2[y][n] - ps[y];
ll maxi = pravo + lavo + min(ps[y] - ps[x], c);
maxi = max(maxi, mpref[x]);
maxi = max(maxi, msuf[y]);
for (ll k = x + 1; k < y; k++) {
maxi = max(maxi, lavo + min(ps[k] - ps[x], ps[y] - ps[k] + c) + d[k]);
maxi = max(maxi, pravo + min(ps[y] - ps[k], ps[k] - ps[x] + c) + d[k]);
//2 situacie -> sme blizsie ku x potom binarne vyhladame najpravejsieho ku ktoremu chceme ist peso
if (ps[k] - ps[x] <= (ps[y] - ps[k])) {
ll l = k, r = y;
while (l < r) {
ll mid = (l + r + 1) / 2;
if (check1(d, ps, k, mid, x, y, c)) l = mid;
else r = mid - 1;
}
//od x po l chceme ist priamo, inak sa chceme otocit
//x az (k-1)
if (x <= (k - 1)) maxi = max(maxi, s1[x][k - 1] + ps[k] + d[k]);
//k+1 az l
if ((k + 1) <= l) maxi = max(maxi, s2[k + 1][l] - ps[k] + d[k]);
//l+1 az y
if ((l + 1) <= y) maxi = max(maxi, s1[l + 1][y] + ps[y] + ps[k] - ps[x] + c + d[k]);
}
else {
//sme blizsie ku y potom binarne vyhladame najlavajsieho ku ktoremu chceme ist peso
ll l = x, r = y;
while (l < r) {
ll mid = (l + r) / 2;
if (check2(d, ps, k, mid, x, y, c)) r = mid;
else l = mid + 1;
}
//k+1 az y
if ((k + 1) <= y) maxi = max(maxi, s2[k + 1][y] - ps[k] + d[k]);
//l az k-1
if (l <= (k - 1)) maxi = max(maxi, s1[l][k - 1] + ps[k] + d[k]);
//x az l-1
if (x <= (l - 1)) maxi = max(maxi, s2[x][l - 1] - ps[x] + c + ps[y] - ps[k] + d[k]);
}
}
if (maxi > mid) continue;
else {
ok = 1;
break;
}
}
if (ok) rv = mid;
else lv = mid + 1;
}
return lv;
}
/*
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) {
cout << odp1 << ' ' << odp2 << '\n';
cout << n << ' ' << c << '\n';
For(i, l.size()) cout << l[i] << ' ';
cout << '\n';
For(i, d.size()) cout << d[i] << ' ';
cout << '\n';
odp1 = find_shortcut_pomale(n, l, d, c);
odp2 = find_shortcut(n, l, d, c);
}
cout << odp2 << '\n';
//return 0;
}
return 0;
}*/
