#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
int n, c;
lint a[1000005], b[1000005];
bool trial(lint x){
lint ps = -1e18, pe = 1e18, ms = -1e18, me = 1e18;
for(int i=0; i<n; i++){
for(int j=i+1; j<n; j++){
if(b[j] - b[i] + a[i] + a[j] > x){
lint r = x - c - a[i] - a[j];
ps = max(ps, b[i] + b[j] - r);
pe = min(pe, b[i] + b[j] + r);
ms = max(ms, b[i] - b[j] - r);
me = min(me, b[i] - b[j] + r);
}
}
}
for(int i=0; i<n; i++){
lint s = max(ps - b[i], b[i] - me);
lint e = min(pe - b[i], b[i] - ms);
if(s <= e && upper_bound(b, b+n, e) != lower_bound(b, b+n, s)) return true;
}
return false;
}
long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c)
{
::n = n;
::c = c;
for(int i=0; i<n; i++){
a[i] = d[i];
if(i >= 1) b[i] = b[i-1] + l[i-1];
}
lint s = 0, e = 1e16;
while(s != e){
lint m = (s+e)/2;
if(trial(m)) e = m;
else s = m+1;
}
return s;
}
