#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;
ll find_shortcut(int n, vector<int> l, vector<int> d, int c) {
vector<ll> p(n, 0);
for(int i=1;i<n;i++) p[i] = p[i-1]+l[i-1];
vector<pair<ll, int>> P(n), P2(n);
for(int i=0;i<n;i++) P[i] = {p[i]-d[i], i}, P2[i] = {p[i]+d[i], i};
sort(P.begin(), P.end()), sort(P2.begin(), P2.end());
vector<array<int, 2>> mx(n);
mx[0] = {P[0].second, -1};
for(int i=1;i<n;i++) {
int u = P[i].second;
mx[i] = mx[i-1];
auto &[f, s] = mx[i];
if(p[u]+d[u] > p[f]+d[f]) s = f, f = u;
else if(s == -1 || p[u]+d[u] > p[s]+d[s]) s = u;
}
auto solve = [&](ll m) {
ll xl = -INF, yl = -INF, xr = INF, yr = INF;
auto diamond = [&](int i, int j, ll m) {
if(i >= j || i < 0) return;
ll x = p[i], y1 = p[j]-m+d[i]+d[j], y2 = p[j]+m-d[i]-d[j];
xl = max(xl, x+y1), yl = max(yl, x-y2);
xr = min(xr, x+y2), yr = min(yr, x-y1);
};
for(int i=0, j=-1;i<n;i++) {
auto [L, id] = P2[i];
while(j+1 < n && P[j+1].first < L-m) j++;
if(j < 0) continue;
diamond(P[0].second, id, m-c);
if(j) diamond(P[1].second, id, m-c);
diamond(mx[j][0], id, m-c);
diamond(mx[j][1], id, m-c);
}
if(xl > xr || yl > yr) return false;
ll PR = -LLONG_MAX;
bool flag = 0;
for(int i=0, j=-1;i<n;i++) {
ll L = max(xl-p[i], yl+p[i]), R = min(xr-p[i], yr+p[i]);
if(!flag && PR > R) flag = 1, j = n-1;
PR = R;
if(!flag) while(j+1 < n && p[j+1] <= R) j++;
if(flag) while(j >= 0 && p[j] > R) j--;
if(0 <= j && j < n && L <= p[j]) return true;
}
return false;
};
ll s = 0, e = 1e12;
while(s <= e) {
ll m = (s+e) >> 1;
if(solve(m)) e = m-1;
else s = m+1;
}
return s;
}
