#include "shortcut.h"
#include <bits/stdc++.h>
//stealing for testing purposes
using namespace std;
using ll = long long;
const ll INF = 1e16;
int n, c;
vector<int> L, R;
vector<ll> P, D;
bool f(ll m) {
ll l=-INF, r=INF, d=-INF, u=INF, m1=INF, m2=INF;
for (int t=0, k=0; t<n; t++) {
int i=L[t];
while (k<n) {
int j=R[k];
if (P[j]-P[i]+D[i]+D[j]<=m) break;
ll im=P[j]-D[j];
if (m1>im) m2=m1, m1=im;
else if (m2>im) m2=im;
k++;
}
int j=(i==R[0]?R[1]:R[0]);
if (P[j]-P[i]+D[i]+D[j]<=m) continue;
ll w=m-c-D[i]-D[j];
ll x=P[i], y=P[j];
l=max(l, x+y-w);
d=max(d, -x+y-w);
w=m-c-D[i]+(m1==P[i]-D[i]?m2:m1);
r=min(r, x+w);
u=min(u, -x+w);
}
//if (n>300000) return false;
for (int i=1, j=1; i<=n; i++) {
ll s=max(l-P[i], d+P[i]);
ll e=min(r-P[i], u+P[i]);
if (s>e) continue;
while (j>1&&P[j-1]>=s) j--;
while (j<=n&&P[j]<s) j++;
if (s<=P[j]&&P[j]<=e) return true;
}
return false;
}
ll find_shortcut(int n, vector<int> l, vector<int> d, int c) {
::n=n;
::c=c;
P={-INF, 0};
for (auto &i:l) P.emplace_back(P.back()+i);
P.emplace_back(INF);
D={0};
for (auto &i:d) D.emplace_back(i);
for (int i=1; i<=n; i++)
L.emplace_back(i),
R.emplace_back(i);
sort(L.begin(), L.end(), [&](int x, int y) { return P[x]-D[x]>P[y]-D[y]; });
sort(R.begin(), R.end(), [&](int x, int y) { return P[x]+D[x]>P[y]+D[y]; });
sort(d.rbegin(), d.rend());
ll s=d[0]+d[1], e=INF;
while (s<e) {
ll m=(s+e)/2;
if (f(m)) e=m;
else s=m+1;
}
return s;
}
