#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 3005;
const long long INF = 1e18;
int n, c;
long long a[N];
long long b[N];
bool check(long long dis) {
long long xmin, xmax, ymin, ymax;
xmin = ymin = -INF, xmax = ymax = INF;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (i != j && abs(a[i] - a[j]) + b[i] + b[j] > dis) {
long long x = a[i] + a[j];
long long y = a[i] - a[j];
if (dis < b[i] + b[j] + c) return 0;
long long len = dis - c - b[i] - b[j];
xmin = max(xmin, x - len);
xmax = min(xmax, x + len);
ymin = max(ymin, y - len);
ymax = min(ymax, y + len);
}
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
long long x = a[i] + a[j];
long long y = a[i] - a[j];
if (xmin <= x && x <= xmax && ymin <= y && y <= ymax) return 1;
}
}
return 0;
}
long long find_shortcut(int _n, vector<int> l, vector<int> d, int _c) {
n = _n, c = _c;
for (int i = 1; i < n; ++i) {
a[i] = a[i - 1] + l[i - 1];
}
for (int i = 0; i < n; ++i) b[i] = d[i];
long long low = 0, high = 1e18;
while (low < high) {
long long mid = (low + high) >> 1;
if (check(mid)) high = mid; else low = mid + 1;
}
return low;
}
