#include <bits/stdc++.h>
using namespace std;
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
using ii = pair<int, int>;
using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;
using pll = pair<ll, ll>;
#define fst first
#define snd second
#define pb push_back
#define eb emplace_back
const ll INF = 1e18;
const int MAX_N = 1e6 + 9;
ll x[MAX_N], d[MAX_N];
int n, c;
int order[2][MAX_N];
ll val(int i, int t) {
if (i == -1) return -INF;
if (t == 0) return x[i] + d[i];
if (t == 1) return -x[i] + d[i];
assert(false);
}
pll intersection(pll a, pll b) {
return pll{max(a.fst, b.fst), min(a.snd, b.snd)};
}
void upd(ii &a, int i, int t) {
if (val(i, t) > val(a.fst, t)) {
a.snd = a.fst;
a.fst = i;
} else if (val(i, t) > val(a.snd, t)) {
a.snd = i;
}
}
bool check(ll R) {
int idx = n - 1;
ii best[2] = {{-1, -1}, {-1, -1}};
pll rangeSum = {-INF, INF}, rangeDiff = {-INF, INF};
auto consider = [&](int i, int j) {
if (i > j) swap(i, j);
if (i == -1) return;
ll v = R - c - d[i] - d[j];
rangeSum = intersection(rangeSum, make_pair(x[i] + x[j] - v,
x[i] + x[j] + v));
rangeDiff = intersection(rangeDiff, make_pair(x[j] - x[i] - v,
x[j] - x[i] + v));
};
forn(i, n) {
while (idx >= 0 && val(order[1][idx], 1) > R - val(order[0][i], 0)) {
forn(j, 2) upd(best[j], order[1][idx], j);
idx--;
}
forn(j, 2) {
int k = best[j].fst;
if (k == order[0][i]) k = best[j].snd;
consider(order[0][i], k);
}
}
if (rangeDiff.fst > rangeDiff.snd || rangeSum.fst > rangeSum.snd) return false;
int j = n, k = 0;
forn(i, n) {
while (j > 0 && x[i] + x[j - 1] >= rangeSum.fst) j--;
while (k < n && x[k] - x[i] < rangeDiff.fst) k++;
int candidate = max({j, k, i + 1});
if (candidate < n && rangeDiff.fst <= x[candidate] - x[i] && x[candidate] - x[i] <= rangeDiff.snd &&
rangeSum.fst <= x[i] + x[candidate] && x[i] + x[candidate] <= rangeSum.snd) {
return true;
}
}
return false;
}
ll find_shortcut(int _n, vi l, vi _d, int _c) {
n = _n, c = _c;
x[0] = 0LL;
forn(i, n - 1) x[i + 1] = x[i] + l[i];
forn(i, n) d[i] = _d[i];
forn(j, 2) forn(i, n) order[j][i] = i;
forn(j, 2) sort(order[j], order[j] + n, [&](const int &lhs, const int &rhs) {
return val(lhs, j) < val(rhs, j);
});
ll lo = 0, hi = x[n - 1] + int(2e9 + 20);
while (hi - lo > 1) {
ll mid = (lo + hi) / 2;
if (check(mid)) hi = mid;
else lo = mid;
}
return hi;
}
