#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;
pll max2(pll x, ll val)
{
if(val >= x.ff)
{
swap(x.ff,x.ss);
x.ff = val;
}
else if(val >= x.ss)
{
x.ss = val;
}
return x;
}
pll min2(pll x, ll val)
{
if(val <= x.ff)
{
swap(x.ff,x.ss);
x.ff = val;
}
else if(val <= x.ss)
{
x.ss = val;
}
return x;
}
bool check(ll K)
{
ll left_plus = -1e18;
ll right_plus = 1e18;
ll left_minus = -1e18;
ll right_minus = 1e18;
// plus
pll cur_max_sum = {-1e18,-1e18};
pll cur_min_dif = {1e18,1e18};
pll cur_max_dif = {-1e18,-1e18};
pll cur_min_sum = {1e18,1e18};
int cur_vsort2 = 0;
vi to_add;
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 = max2(cur_max_sum,P[v]+D[v]);
cur_min_dif = min2(cur_min_dif,P[v]-D[v]);
cur_max_dif = max2(cur_max_dif,-P[v]+D[v]);
cur_min_sum = min2(cur_min_sum,-P[v]-D[v]);
}
int v = it.ss;
left_plus = max(left_plus,(P[v]+D[v] != cur_max_sum.ff ? cur_max_sum.ff : cur_max_sum.ss)+P[v]+D[v]+C-K);
right_plus = min(right_plus,(P[v]-D[v] != cur_min_dif.ff ? cur_min_dif.ff : cur_min_dif.ss)+P[v]-D[v]-C+K);
left_minus = max(left_minus,(-P[v]+D[v] != cur_max_dif.ff ? cur_max_dif.ff : cur_max_dif.ss)+P[v]+D[v]+C-K);
right_minus = min(right_minus,(-P[v]-D[v] != cur_min_sum.ff ? cur_min_sum.ff : cur_min_sum.ss)+P[v]-D[v]-C+K);
}
if(left_plus > right_plus || left_minus > right_minus) return 0;
rep(i,n)
{
rep2(j,i+1,n-1)
{
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*2;
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;
}
