#pragma GCC optimize("O3")
#pragma GCC optimize("fast-math")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,sse4,abm,avx,avx2")
#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;
int n;
ll 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;
int i1=-1, i2=-1;
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) tie(m2, i2)=tie(m1, i1), tie(m1, i1)=tie(im, j);
else if (m2>im) tie(m2, i2)=tie(im, j);
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]+(i1==i?(P[i2]-D[i2]):(P[i1]-D[i1]));
r=min(r, x+w);
u=min(u, -x+w);
if (l>r||d>u) 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<=n&&P[j]<s) j++;
while (j>=1&&P[j-1]>=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;
}
