#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];
auto find = [&](int i, int j, ll m) -> array<ll, 4> {
ll x = p[i], yl = p[j]-m+d[i]+d[j], yr = p[j]+m-d[i]-d[j];
return {x+yl, x-yr, x+yr, x-yl};
};
auto P = p; sort(P.begin(), P.end());
auto solve = [&](ll m) {
ll xl = -INF, yl = -INF, xr = INF, yr = INF;
for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) if(p[j]-p[i]+d[j]+d[i] > m) {
auto [XL, YL, XR, YR] = find(i, j, m-c);
// cout << i << " " << j << " : " << XL << " " << YL << " " << XR << " " << YR << "\n";
xl = max(xl, XL), yl = max(yl, YL);
xr = min(xr, XR), yr = min(yr, YR);
if(xl > xr || yl > yr) return false;
}
for(int u : P) {
ll L = min(xl-u, yl+u), R = (xr-u, yr+u);
auto it = lower_bound(P.begin(), P.end(), L);
if(it != P.end() && *it <= R) return true;
}
return false;
};
ll s = 0, e = INF;
while(s <= e) {
ll m = (s+e) >> 1;
if(solve(m)) e = m-1;
else s = m+1;
}
return s;
}
