#include <bits/stdc++.h>
#include "shortcut.h"
template <class T>
using Vec = std::vector<T>;
using ll = long long;
constexpr ll INF = std::numeric_limits<ll>::max() / 2;
template <class T>
void setmin(T& lhs, const T& rhs) {
if (lhs > rhs) {
lhs = rhs;
}
}
template <class T>
void setmax(T& lhs, const T& rhs) {
if (lhs < rhs) {
lhs = rhs;
}
}
ll find_shortcut(int n, Vec<int> l, Vec<int> d, int c) {
Vec<ll> x(n);
for (int i = 1; i < n; ++i) {
x[i] = x[i - 1] + l[i - 1];
}
const auto check = [&](const ll threshold) -> bool {
ll sum_min = -INF, sum_max = INF;
ll dif_min = -INF, dif_max = INF;
for (int i = 0; i < n; ++i) {
if (d[i] > threshold) {
return false;
}
for (int j = i + 1; j < n; ++j) {
if (d[i] + d[j] + (x[j] - x[i]) > threshold) {
if (d[i] + d[j] + c > threshold) {
return false;
}
setmin(sum_max, (x[i] - d[i]) + (x[j] - d[j]) + threshold - c);
setmax(sum_min, (x[i] + d[i]) + (x[j] + d[j]) + c - threshold);
setmin(dif_max, -(x[i] + d[i]) + (x[j] - d[j]) + threshold - c);
setmax(dif_min, -(x[i] - d[i]) + (x[j] + d[j]) + c - threshold);
}
}
}
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (sum_min <= x[i] + x[j] and x[i] + x[j] <= sum_max and dif_min <= x[j] - x[i] and x[j] - x[i] <= dif_max) {
return true;
}
}
}
return false;
};
ll ok = INF, ng = 0;
while (ok - ng > 1) {
const auto md = (ok + ng) / 2;
(check(md) ? ok : ng) = md;
}
return ok;
}
