#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
//transform (x, y) into (x+y, -x+y) with sizeof square = 2*d
int n;
vector<int> l, d;
int c;
vector< ll > X;
struct square
{
ll x, y, d;
//bottom left coordinates and size
square(ll _x, ll _y, ll _d)
{
x = _x; y = _y; d = _d;
}
};
vector<square> all;
bool works()
{
bool bad = false;
for(auto sq : all)
{
if(sq.d< 0) bad = true;
}
if(bad) return false;
if(all.empty()) return true;
ll xmin = -1e18, ymin = -1e18, xmax = 1e18, ymax = 1e18;
for(auto sq : all)
{
ll sqx = sq.x, sqy = sq.y, sqd = sq.d;
xmin = max(xmin, sqx);
xmax = min(xmax, sqx+sqd);
ymin = max(ymin, sqy);
ymax = min(ymax, sqy+sqd);
}
//printf("survival");
for(int a = 0; a< n; a++)
{
for(int b = a+1; b< n; b++)
{
ll _x = X[a], _y = X[b];
ll bx = _x+_y, by = -_x+_y;
if(xmin<= bx && bx<= xmax && ymin<= by && by<= ymax) return true;
}
}
return false;
}
ll find_shortcut(int _n, vector<int> _l, vector<int> _d, int _c)
{
n = _n; l = _l; d = _d; c = _c;
X.resize(n); X[0] = 0;
for(int i = 1; i< n; i++)
{
X[i] = X[i-1] + l[i-1];
}
ll lo = 0, hi = 1e15;
while(lo< hi)
{
ll mid = (lo+hi)/2;
all.clear();
//printf("test %lld ", mid);
for(int a = 0; a< n; a++)
{
for(int b = a+1; b< n; b++)
{
if(X[b]-X[a]+d[a]+d[b]<= mid) continue;
ll _x = X[a], _y = X[b];
ll bx = _x, by = _y-(mid-d[a]-d[b]-c);
all.pb(square(bx+by, -bx+by, 2LL*(mid-d[a]-d[b]-c)));
}
}
if(works())
{
//printf("works");
hi = mid;
}
else lo = mid+1;
//printf("\n");
}
return lo;
}
