#include "shortcut.h"
#include<stdio.h>
#include<algorithm>
#include<cstdlib>
#include<vector>
#define N_ 1010000
using namespace std;
int n, be[N_], ed[N_];
long long S[N_], P[N_], TL;
struct point{
long long a, b;
int num;
bool operator<(const point &p)const{
return a<p.a;
}
}AA[N_], BB[N_];
bool Pos(long long d){
int pv, i;
long long b1 = -1e18, e1 = 1e18, b2 = -1e18, e2 = 1e18;
long long Mx1 = -1e18, Mx2 = -1e18;
int pv1 = -1, pv2 = -1;
pv = n+1;
for(i=1;i<=n;i++){
while(pv>1 && BB[pv-1].a + AA[i].a > d){
pv--;
if(Mx1 < BB[pv].b){
Mx2 = Mx1; pv2 = pv1;
Mx1 = BB[pv].b, pv1 = BB[pv].num;
}
else if(Mx2 < BB[pv].b){
Mx2 = BB[pv].b, pv2 = BB[pv].num;
}
}
if(AA[i].num == pv1) b1 = max(b1, AA[i].a + Mx2 + TL - d);
else b1 = max(b1, AA[i].a + Mx1 + TL - d);
if(pv <= n){
if(AA[i].num == BB[n].num){
if(pv < n) e1 = min(e1, -(AA[i].b + BB[n-1].a) + d - TL);
}
else e1 = min(e1, -(AA[i].b + BB[n].a) + d - TL);
}
if(AA[i].num == pv1) b2 = max(b2, AA[i].b + Mx2 + TL - d);
else b2 = max(b2, AA[i].b + Mx1 + TL - d);
if(pv <= n){
if(AA[i].num == BB[n].num){
if(pv < n) e2 = min(e2, -(AA[i].a + BB[n-1].a) + d - TL);
}
else e2 = min(e2, -(AA[i].a + BB[n].a) + d - TL);
}
}
if(b1>e1 || b2>e2)return false;
pv1 = n+1, pv2 = 1;
for(i=1;i<=n;i++){
while(pv1 > 1 && b1-S[i] <= S[pv1-1])pv1--;
while(pv2 <= n && S[i]+b2 > S[pv2])pv2++;
be[i] = max(pv2,pv1);
}
pv1 = n, pv2 = 0;
for(i=1;i<=n;i++){
while(pv1 && e1-S[i] < S[pv1])pv1--;
while(pv2 < n && S[i]+e2 >= S[pv2+1])pv2++;
ed[i] = min(pv2,pv1);
if(ed[i] >= be[i] && (ed[i]!=i || be[i]!=i))return true;
}
return false;
}
long long find_shortcut(int N, vector<int> l, vector<int> d, int c)
{
TL = c;
n = N;
int i;
long long mx = 0;
long long b = 0, e = 0, mid, res = 0;
for(i=1;i<=n;i++){
if(i!=1)S[i] = S[i-1] + l[i-2];
P[i] = d[i-1];
AA[i].a = S[i]+P[i], AA[i].b = P[i]-S[i], AA[i].num = i;
BB[i].a = P[i]-S[i], BB[i].b = S[i]+P[i], BB[i].num = i;
if(b<mx+P[i])b=mx+P[i];
mx = max(mx,P[i]);
}
sort(AA+1,AA+n+1);
sort(BB+1,BB+n+1);
e = b+S[n];
while(b<=e){
mid = (b+e)/2;
if(Pos(mid)){
res = mid;
e = mid - 1;
}
else b = mid + 1;
}
return res;
}
