#include <bits/stdc++.h>
bool check(long long mid, const std::vector <long long> her[2], const std::vector <long long>& pre, int c, int n) {
long long ls = -(1LL << 60);
long long rs = 1LL << 60;
long long ld = ls;
long long rd = rs;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) {
continue;
}
if (her[0][j] - her[1][i] <= mid) {
continue;
}
ls = std::max(ls, her[0][i] + her[0][j] + c - mid);
rs = std::min(rs, her[1][i] + her[1][j] - c + mid);
ld = std::max(ld, her[0][i] - her[1][j] + c - mid);
rd = std::min(rd, her[1][i] - her[0][j] - c + mid);
}
}
if (ls > rs || ld > rd) {
return false;
}
for (int i = 0; i < n - 1; i++) {
long long l = std::max(ls - pre[i], pre[i] - rd);
long long r = std::min(rs - pre[i], pre[i] - ld);
if (l > r) {
continue;
}
int lb = std::lower_bound(pre.begin() + i + 1, pre.end(), l) - pre.begin();
if (lb != n && pre[lb] <= r) {
return true;
}
}
return false;
}
long long find_shortcut(int n, std::vector <int> el, std::vector <int> d, int c) {
std::vector <long long> pre(n, 0);
for (int i = 1; i < n; i++) {
pre[i] = pre[i - 1] + el[i - 1];
}
std::vector <long long> her[2];
her[0].resize(n);
her[1].resize(n);
for (int i = 0; i < n; i++) {
her[0][i] = pre[i] + d[i];
her[1][i] = pre[i] - d[i];
}
std::vector <int> ord[2];
for (int i = 0; i < 2; i++) {
ord[i].resize(n);
std::iota(ord[i].begin(), ord[i].end(), 0);
std::sort(ord[i].begin(), ord[i].end(), [&] (int u, int v) -> bool { return her[i][u] < her[i][v]; });
}
long long l = 0, r = 1LL << 55;
while (l <= r) {
long long mid = (l + r) >> 1;
if (check(mid, her, pre, c, n)) {
r = mid - 1;
} else {
l = mid + 1;
}
}
return l;
}
