#include <bits/stdc++.h>
#include "shortcut.h"
using namespace std;
const long long MAX = 1'000'000'000'000'000'000;
const int N = 3'000 + 10;
struct Rec {
long long x, y, u, v;
Rec(long long x = -MAX, long long y = -MAX, long long u = MAX, long long v = MAX) : x(x), y(y), u(u), v(v) {}
};
Rec merge(const Rec& a, const Rec& b) {
return Rec(max(a.x, b.x), max(a.y, b.y), min(a.u, b.u), min(a.v, b.v));
}
long long find_shortcut(int n, vector<int> l, vector<int> d, int c) {
vector<long long> p(n);
for (int i = 1; i < n; ++i) p[i] = p[i - 1] + l[i - 1];
auto chk = [&](long long mid) {
auto calRec = [&](int i, int j, long long c) {
return Rec(p[i] + p[j] + d[i] + d[j] - c,
p[i] - p[j] + d[i] + d[j] - c,
p[i] + p[j] - d[i] - d[j] + c,
p[i] - p[j] - d[i] - d[j] + c);
};
Rec rec;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (p[j] - p[i] + d[i] + d[j] <= mid) continue;
rec = merge(rec, calRec(i, j, mid - c));
}
}
if (rec.x > rec.u || rec.y > rec.v) return false;
for (int i = 0; i < n; ++i) {
long long L = max(rec.x - p[i], rec.y + p[i]),
R = min(rec.u - p[i], rec.v + p[i]);
auto it = lower_bound(p.begin(), p.end(), L);
if (it != p.end() && *it <= R) return true;
}
return false;
};
long long le = 0, ri = MAX, ret = MAX;
while (le <= ri) {
auto mid = (le + ri) >> 1;
if (chk(mid)) ri = mid - 1, ret = mid;
else le = mid + 1;
}
return ret;
}
