#include "shortcut.h"
#include <vector>
#include <algorithm>
using namespace std;
vector<long long> qs;
vector<int> d;
vector<int> posj; //sort by qs[j]+d[j]
vector<int> posi; //sort by qs[i]-d[i]
bool work(long long k,long long c) {
long long lft=-1e18;
long long rgt=1e18;
long long top=1e18;
long long bot=-1e18;
int n=(int)qs.size();
int _i=0;
for (int _j=0;_j<n;_j++) {
int j=posj[_j];
while (_i<n&&qs[j]-qs[posi[_i]]+d[j]+d[posi[_i]]>k) {
int i=posi[_i];
lft=max(lft,(qs[i]+d[i])-(qs[j]-d[j])-k+c);
rgt=min(rgt,(qs[i]-d[i])-(qs[j]+d[j])+k-c);
top=min(top,(qs[i]-d[i])+(qs[j]-d[j])+k-c);
bot=max(bot,(qs[i]+d[i])+(qs[j]+d[j])-k+c);
_i++;
}
}
if (lft>rgt||bot>top) return false;
long long x,y;
for (int i=0;i<n;i++) {
for (int j=i+1;j<n;j++) {
x=qs[i]-qs[j];
y=qs[i]+qs[j];
if (lft<=x&&x<=rgt&&bot<=y&&y<=top) return true;
}
}
return false;
}
long long find_shortcut(int n, vector<int> l, vector<int> d, int c)
{
qs.resize(n,0);
for (int i=1;i<n;i++) {
qs[i]=l[i-1];
qs[i]+=qs[i-1];
}
::d=d;
posj.resize(n,0);
posi.resize(n,0);
for (int i=0;i<n;i++) {
posi[i]=i;
posj[i]=i;
}
sort(posj.begin(),posj.end(),[&](const int &a, const int &b) {
return qs[a]+d[a]<qs[b]+d[b];
});
sort(posi.begin(),posi.end(),[&](const int &a, const int &b) {
return qs[a]-d[a]<qs[b]-d[b];
});
long long lo=0;
long long hi=1e15;
long long mid;
while (lo<hi) {
mid=(lo+hi)>>1;
if (work(mid,c)) {
hi=mid;
} else {
lo=mid+1;
}
}
return lo;
}
