#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
#include "shortcut.h"
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
const int N = (int)(1e6) + 5;
const ll oo = 1e18 + 5;
ll xx[N];
ll x[N];
ll y[N];
int ind[N];
int d[N];
int n,c;
vector < ll > ss;
struct st
{
ll mxsum,mnsum;
ll mxdif,mndif;
st(void)
{
mxsum = mxdif = oo;
mnsum = mndif = -oo;
}
st(ll a,ll b,ll c,ll d) : mxsum(a),mnsum(b),mxdif(c),mndif(d) {}
};
const st shit = st(oo,-oo,oo,-oo);
st Comb(st a,st b)
{
st c;
c.mxsum = min(a.mxsum,b.mxsum);
c.mnsum = max(a.mnsum,b.mnsum);
c.mxdif = min(a.mxdif,b.mxdif);
c.mndif = max(a.mndif,b.mndif);
return c;
}
st t[N * 4];
void U(int i,st v)
{
for (;i;i -= i&(-i))
t[i] = Comb(t[i],v);
}
st Q(int i)
{
st ans;
for (;i <= n;i += i&(-i))
ans = Comb(ans,t[i]);
return ans;
}
int F(ll dist)
{
ll mxsum = oo;
ll mxdif = oo;
ll mnsum = -oo;
ll mndif = -oo;
for (int i = 1;i <= n;++i)
t[i] = shit;
const int SZ = ss.size();
for (int i = n;i;--i)
{
int index = lower_bound(all(ss),y[i] + dist + 1) - ss.begin() + 1;
if (index <= SZ)
{
st cnt = Q(index);
smin(mxsum,dist - c + y[i] + cnt.mxsum);
smax(mnsum,c - dist + x[i] + cnt.mnsum);
smin(mxdif,dist - c + cnt.mxdif - x[i]);
smax(mndif,c - dist + cnt.mndif - y[i]);
}
index = ind[i];
U(index,st(y[i],x[i],y[i],x[i]));
}
set < ll > S;
for (int i = n;i;--i)
{
ll l1 = mndif + xx[i];
ll r1 = mxdif + xx[i];
smax(l1,mnsum - xx[i]);
smin(r1,mxsum - xx[i]);
auto index = S.lower_bound(l1);
if (index != S.end() && *index <= r1)
return 1;
S.insert(xx[i]);
}
return 0;
}
ll find_shortcut(int shit0,vi shit1,vi shit2,int shit3)
{
n = shit0;
c = shit3;
for (int i = 2;i <= n;++i)
x[i] = x[i - 1] + shit1[i - 2];
for (int i = 1;i <= n;++i)
d[i] = shit2[i - 1];
for (int i = 1;i <= n;++i)
{
xx[i] = x[i];
y[i] = x[i] - d[i];
x[i] = x[i] + d[i];
}
for (int i = 1;i <= n;++i)
ss.pb(x[i]);
sort(all(ss));
ss.resize(unique(all(ss)) - ss.begin());
for (int i = 1;i <= n;++i)
ind[i] = lower_bound(all(ss),x[i]) - ss.begin() + 1;
ll ans = oo;
for (ll k = 1ll << 60;k;k /= 2)
if (ans >= k && F(ans - k))
ans -= k;
return ans;
}
