#include "shortcut_c.h"
#define N 1000000
#define INF 0x3f3f3f3f3f3f3f3f
long long min(long long a, long long b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }
long long abs_(long long a) { return a > 0 ? a : -a; }
long long find_shortcut(int n, int *ll, int *dd, int c) {
static long long xx[N];
int i, j, k, l;
long long lower, upper;
for (i = 1; i < n; i++)
xx[i] = xx[i - 1] + ll[i - 1];
lower = -1, upper = xx[n - 1] + 2000000000;
while (upper - lower > 1) {
long long d = (lower + upper) / 2, w, x, y, z;
int can;
w = x = y = z = INF;
for (k = 0; k < n; k++)
for (l = k + 1; l < n; l++)
if (dd[k] + dd[l] + xx[l] - xx[k] > d) {
/* dd[k] + dd[l] + |xx[k] - xx[i]| + c + |xx[l] - xx[j]| <= d
*
* max(xx[k] - xx[i], xx[i] - xx[k]) + max(xx[l] - xx[j], xx[j] - xx[l])
* <= d - (dd[k] + dd[l] + c)
*
* xx[k] - xx[i] + xx[l] - xx[j] <= d - (dd[k] + dd[l] + c)
* xx[k] - xx[i] + xx[j] - xx[l] <= d - (dd[k] + dd[l] + c)
* xx[i] - xx[k] + xx[l] - xx[j] <= d - (dd[k] + dd[l] + c)
* xx[i] - xx[k] + xx[j] - xx[l] <= d - (dd[k] + dd[l] + c)
*
* - xx[i] - xx[j] <= d - (dd[k] + dd[l] + c + xx[k] + xx[l])
* - xx[i] + xx[j] <= d - (dd[k] + dd[l] + c + xx[k] - xx[l])
* + xx[i] - xx[j] <= d - (dd[k] + dd[l] + c - xx[k] + xx[l])
* + xx[i] + xx[j] <= d - (dd[k] + dd[l] + c - xx[k] - xx[l]) */
w = min(w, d - (dd[k] + dd[l] + c + xx[k] + xx[l]));
x = min(x, d - (dd[k] + dd[l] + c + xx[k] - xx[l]));
y = min(y, d - (dd[k] + dd[l] + c - xx[k] + xx[l]));
z = min(z, d - (dd[k] + dd[l] + c - xx[k] - xx[l]));
}
can = 0;
for (i = 0; i < n; i++)
for (j = i + 1; j < n; j++)
if (- xx[i] - xx[j] <= w && - xx[i] + xx[j] <= x && + xx[i] - xx[j] <= y && + xx[i] + xx[j] <= z) {
can = 1;
goto out;
}
out:
if (can)
upper = d;
else
lower = d;
}
return upper;
}
