#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];
// cout << yl << " " << yr << "\n";
return {x+yl, x-yr, x+yr, x-yl};
};
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 i=0;i<n;i++) for(int j=i+1;j<n;j++) {
auto [XL, YL, XR, YR] = find(i, j, d[i]+d[j]);
if(xl <= XL && XR <= xr && yl <= YL && YR <= yr) 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;
}
