#include "shortcut.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;
ll P[1000001];
ll D[1000001];
ll C;
int n;
vector<pll> vsort1;
vector<pll> vsort2;
bool check(ll K)
{
ll left_plus = -1e18;
ll right_plus = 1e18;
ll left_minus = -1e18;
ll right_minus = 1e18;
// plus
ll cur_max_sum = -1e18;
ll cur_min_dif = 1e18;
ll cur_max_dif = -1e18;
ll cur_min_sum = 1e18;
int cur_vsort2 = 0;
forall(it,vsort1)
{
while(cur_vsort2 < siz(vsort2) && vsort2[cur_vsort2].ff + it.ff > K)
{
int v = vsort2[cur_vsort2].ss;
cur_vsort2++;
cur_max_sum = max(cur_max_sum,P[v]+D[v]);
cur_min_dif = min(cur_min_dif,P[v]-D[v]);
cur_max_dif = max(cur_max_dif,-P[v]+D[v]);
cur_min_sum = min(cur_min_sum,-P[v]-D[v]);
}
int v = it.ss;
left_plus = max(left_plus,cur_max_sum+P[v]+D[v]+C-K);
right_plus = min(right_plus,cur_min_dif+P[v]-D[v]-C+K);
left_minus = max(left_minus,cur_max_dif+P[v]+D[v]+C-K);
right_minus = min(right_minus,cur_min_sum+P[v]-D[v]-C+K);
}
rep(i,n)
{
rep2(j,i+1,n)
{
ll sum = P[i]+P[j];
ll dif = P[j]-P[i];
if(sum >= left_plus && sum <= right_plus && dif >= left_minus && dif <= right_minus) return 1;
}
}
return 0;
}
ll find_shortcut(int N, vi L, vi d, int c)
{
n = N;
C = c;
ll sum = 0;
vl Ds;
rep(i,n)
{
Ds.pb(d[i]);
D[i] = d[i];
P[i] = sum;
sum += L[i];
vsort1.pb({P[i]+D[i],i});
vsort2.pb({-P[i]+D[i],i});
}
sort(all(vsort1));
sort(all(vsort2));
reverse(all(vsort2));
sort(all(Ds));
reverse(all(Ds));
ll l = Ds[0]+Ds[1];
ll r = 1e9*(ll)n;
ll ans = 0;
while(l <= r)
{
ll mid = (l+r)/2;
if(check(mid))
{
ans = mid;
r = mid-1;
}
else
{
l = mid+1;
}
}
return ans;
}
