#include <cstdio>
#include <map>
#include <set>
#include <vector>
using namespace std;
using ll=long long;
const int maxn = int(1e6) + 10;
const ll inf = ll(4e15);
int n; ll L;
ll P[maxn], D[maxn], A[maxn], B[maxn];
void insert_downstair(map<ll,ll> &m, ll x, ll y) {
auto it = m.lower_bound(x);
if (it != m.end() && y <= it->second) return;
if (it->first == x) it->second = y;
else it = m.insert(it, pair<ll,ll>{x, y});
while (it != m.begin()) {
auto pr = prev(it);
if (pr->second <= y) m.erase(pr);
else break;
}
}
ll get_max_y_where_x_geq(map<ll,ll> &m, ll xmin) {
auto it = m.lower_bound(xmin);
if (it == m.end()) return -inf;
return it->second;
}
bool can_satisfy(ll V) {
ll plus_min = -inf, plus_max = inf;
ll minus_min = -inf, minus_max = inf;
map<ll,ll> setA, setB;
for (int i=n-1; 0<=i; --i) {
ll maxAj = get_max_y_where_x_geq(setA, V-B[i]+1),
maxBj = get_max_y_where_x_geq(setB, V-B[i]+1);
plus_min = max(plus_min, A[i]+maxAj-V+L);
plus_max = min(plus_max, V-L-B[i]-maxBj);
minus_min = max(minus_min, A[i]+maxBj-V+L);
minus_max = min(minus_max, V-L-B[i]-maxAj);
insert_downstair(setA, A[i], A[i]);
insert_downstair(setB, A[i], B[i]);
}
setA.clear(); setB.clear();
set<ll> px;
for (int y=0; y<n; ++y) {
ll pxmin = max(plus_min - P[y], minus_min + P[y]);
ll pxmax = min(plus_max - P[y], minus_max + P[y]);
auto it = px.lower_bound(pxmin);
if (it != px.end() && (*it) <= pxmax) return true;
px.insert(P[y]);
}
return false;
}
ll find_shortcut(int n_, vector<int> l, vector<int> d, int c) {
n = n_; L = c;
copy(d.begin(), d.end(), D);
for (int i=1; i<n; ++i) P[i] = P[i-1] + l[i-1];
for (int i=0; i<n; ++i) A[i] = D[i] + P[i], B[i] = D[i] - P[i];
ll left = 0, right = inf;
while (left + 1 < right) {
ll md = (left + right) / 2;
(can_satisfy(md) ? right : left) = md;
}
return right;
}
