#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 1000005
typedef long long lld;
int N, C;
int L[MAXN], D[MAXN];
int A[MAXN], B[MAXN];
lld X[MAXN], V1[MAXN], V2[MAXN];
int proc(lld d)
{
lld p = -1e18, q = 1e18, r = -1e18, s = 1e18;
lld mn1 = 1e18, mn2 = 1e18;
for (int i=1,j=1;i<=N;i++){
while (j <= N && V1[B[j]] > d+V2[A[i]]){
lld v = V2[B[j]];
if (mn1 > v) mn2 = mn1, mn1 = v;
else if (mn2 > v) mn2 = v;
j++;
}
if (j == 1 || j == 2 && B[1] == A[i]) continue;
int x = A[i], y = B[1] == A[i] ? B[2] : B[1];
lld v = d - D[x] - D[y] - C;
q = min(q, X[x]-X[y]+v);
r = max(r, X[x]+X[y]-v);
v = d - D[x] - C + (mn1 == V2[x] ? mn2 : mn1);
p = max(p, X[x]-v);
s = min(s, X[x]+v);
if (p > q || r > s) return 0;
}
// Check there is exact station for l, r we have
int t = 1;
for (int i=1;i<=N;i++){
lld a = max(p + X[i], r - X[i]);
lld b = min(q + X[i], s - X[i]);
while (t > 1 && X[t-1] >= a) t--;
while (t <= N && X[t] < a) t++;
if (t <= N && X[t] <= b) return 1;
}
return 0;
}
lld find_shortcut(int n, vector<int> l, vector<int> d, int c)
{
N = n; C = c;
int mx1 = 0, mx2 = 0;
for (int i=1;i<=N;i++){
L[i] = l[i-1]; D[i] = d[i-1];
X[i] = X[i-1] + L[i-1];
V1[i] = X[i] + D[i]; V2[i] = X[i] - D[i];
if (mx1 < D[i]) mx2 = mx1, mx1 = D[i];
else if (mx2 < D[i]) mx2 = D[i];
}
V1[0] = V2[0] = 1e18;
for (int i=1;i<=N;i++) A[i] = B[i] = i;
sort(A+1, A+N+1, [](const int &a, const int &b){
return V2[a] > V2[b];
});
sort(B+1, B+N+1, [](const int &a, const int &b){
return V1[a] > V1[b];
});
lld s = mx1+mx2, e = 1e16, ans;
while (s <= e){
lld m = (s+e)>>1;
if (proc(m)) e = m-1, ans = m;
else s = m+1;
}
return ans;
}
