#include "shortcut.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll INF=1e18+7;
const int LIM=1e6+7;
ll P[LIM], T[LIM], prefm[LIM], n, C;
bool check(ll k) {
ll xpy_dol=-INF, xpy_gora=INF, ymx_dol=0, ymx_gora=INF;
for(int b=1; b<n; ++b) {
if(prefm[b-1]>k-P[b]-T[b]) {
xpy_gora=min(xpy_gora, -prefm[b-1]+P[b]-T[b]+k-C);
ymx_dol=max(ymx_dol, prefm[b-1]+P[b]+T[b]-k+C);
}
rep(a, b) if(T[a]-P[a]>k-P[b]-T[b]) {
xpy_dol=max(xpy_dol, P[a]+T[a]+P[b]+T[b]-k+C);
ymx_gora=min(ymx_gora, -P[a]-T[a]+P[b]-T[b]+k-C);
}
}
rep(b, n) rep(a, b) if(xpy_dol<=P[a]+P[b] && P[a]+P[b]<=xpy_gora && ymx_dol<=P[b]-P[a] && P[b]-P[a]<=ymx_gora) return true;
return false;
}
ll find_shortcut(int _n, vector<int>_l, vector<int>_d, int _c) {
n=_n; C=_c;
rep(i, n-1) P[i+1]=P[i]+_l[i];
rep(i, n) T[i]=_d[i];
rep(i, n) {
prefm[i]=T[i]-P[i];
if(i) prefm[i]=max(prefm[i], prefm[i-1]);
}
ll po=0, ko=3000000000000000;
while(po<ko) {
ll sr=(po+ko)/2;
if(check(sr)) ko=sr; else po=sr+1;
}
return po;
}
