#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 find_shortcut(int n, int *ll, int *dd, int c) {
static long long xx[N], yy[N], zz[N];
int i, j, k, l, d1, d2;
long long lower, upper;
for (i = 1; i < n; i++)
xx[i] = xx[i - 1] + ll[i - 1];
d1 = d2 = 0;
for (i = 0; i < n; i++) {
yy[i] = dd[i] - xx[i], zz[i] = dd[i] + xx[i];
if (d1 < dd[i])
d2 = d1, d1 = dd[i];
else if (d2 < dd[i])
d2 = dd[i];
}
lower = d1 + d2 - 1, upper = xx[n - 1] + d1 + d2;
while (upper - lower > 1) {
long long d = (lower + upper) / 2, p, q, r, s;
int can, j1, j2;
p = q = r = s = INF;
for (k = 0; k < n; k++)
for (l = k + 1; l < n; l++)
if (yy[k] + zz[l] > 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]) */
p = min(p, d - (zz[k] + zz[l] + c));
q = min(q, d - (zz[k] + yy[l] + c));
r = min(r, d - (yy[k] + zz[l] + c));
s = min(s, d - (yy[k] + yy[l] + c));
}
can = 0;
for (i = 0, j1 = -1, j2 = n - 1; i < n; i++) {
while (j1 + 1 < n && - xx[i] + xx[j1 + 1] <= q)
j1++;
while (j2 >= 0 && + xx[i] + xx[j2] > s)
j2--;
j = min(j1, j2);
if (i < j && - xx[i] - xx[j] <= p && + xx[i] - xx[j] <= r) {
can = 1;
break;
}
}
if (can)
upper = d;
else
lower = d;
}
return upper;
}
