#include "shortcut.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
template<class T>void minimize(T& a, T b){
if(a > b){
a = b;
}
}
template<class T>void maximize(T& a, T b){
if(a < b){
a = b;
}
}
const int lim = 1e6 + 5;
int n, c, l[lim], d[lim];
ll f[lim];
namespace sub12{
const int lim = 205;
ll dist[lim][lim];
void add_edge(int u, int v, int w){
dist[u][v] = dist[v][u] = w;
}
ll solve(){
memset(dist, 0x0f, sizeof(dist));
for(int i = 1; i < n; i++){
add_edge(i, i + 1, l[i]);
}
int N = n + 1;
for(int i = 1; i <= n; i++){
if(d[i] > 0){
add_edge(i, N++, d[i]);
}
}
for(int i = 1; i < N; i++){
dist[i][i] = 0;
}
for(int k = 1; k < N; k++){
for(int u = 1; u < N; u++){
for(int v = 1; v < N; v++){
minimize(dist[u][v], dist[u][k] + dist[k][v]);
}
}
}
ll ans = INF;
for(int i = 1; i < n; i++){
for(int j = i + 1; j <= n; j++){
ll diam = 0;
for(int u = 1; u < N; u++){
for(int v = u + 1; v < N; v++){
maximize(diam, min(dist[u][v], min(dist[u][i] + dist[j][v], dist[u][j] + dist[i][v]) + c));
}
}
minimize(ans, diam);
}
}
return ans;
}
}
namespace sub34{
const int lim = 505;
ll min_fd[lim][lim], max_du[lim][lim];
ll solve(){
memset(min_fd, 0x0f, sizeof(min_fd));
f[1] = 0;
for(int i = 1; i < n; i++){
f[i + 1] = f[i] + l[i];
}
for(int i = 1; i <= n; i++){
min_fd[i][i] = f[i] - d[i];
}
for(int l = n - 1; l > 0; l--){
for(int r = l + 1; r <= n; r++){
min_fd[l][r] = min(min_fd[l + 1][r], min_fd[l][l]);
}
}
memset(max_du, -0x0f, sizeof(max_du));
for(int u = 1; u <= n; u++){
for(int i = 1; i <= u; i++){
max_du[u][i] = max(max_du[u][i - 1], f[u] - f[i] + d[i]);
}
for(int i = u + 1; i <= n; i++){
max_du[u][i] = max(max_du[u][i - 1], f[i] - f[u] + d[i]);
}
}
ll ans = INF;
for(int u = 1, max_d = *max_element(d + 1, d + n + 1); u < n; u++){
for(int v = u + 1; v <= n; v++){
ll diam = max_d;
for(int j = 2; j < u; j++){
maximize(diam, f[j] + d[j] - min_fd[1][j - 1]);
}
for(int j = u, i = u; j <= v; j++){
while(i < j && f[j] - f[i] > (f[i] - f[u]) + (f[v] - f[j]) + c){
i++;
}
if(i > u){
maximize(diam, max(f[j] + d[j] - min_fd[i][j - 1], f[v] - f[j] + d[j] + c + max_du[u][i - 1]));
}
else{
maximize(diam, f[j] + d[j] - min_fd[1][j - 1]);
}
}
int pi = -1;
for(int i = v; i >= u; i--){
if(f[i] - f[u] + c < f[v] - f[i]){
pi = i;
break;
}
}
for(int j = v + 1; j <= n; j++){
if(pi == -1){
maximize(diam, f[j] + d[j] - min_fd[1][j - 1]);
}
else{
maximize(diam, max(f[j] + d[j] - min_fd[pi + 1][j - 1], f[j] - f[v] + d[j] + c + max_du[u][pi]));
}
}
minimize(ans, diam);
}
}
return ans;
}
}
namespace sub5{
const int lim = 3e3 + 5;
bool check(ll k){
ll x1 = -INF, x2 = INF, y1 = -INF, y2 = INF;
for(int i = 1; i < n; i++){
for(int j = i + 1; j <= n; j++){
if(f[j] - f[i] + d[i] + d[j] > k){
ll delta = k - d[i] - d[j] - c, px = f[i] + f[j], py = f[i] - f[j];
if(delta < 0){
return false;
}
maximize(x1, px - delta);
minimize(x2, px + delta);
maximize(y1, py - delta);
minimize(y2, py + delta);
}
}
}
for(int i = 1; i < n; i++){
for(int j = i + 1; j <= n; j++){
ll px = f[i] + f[j], py = f[i] - f[j];
if(x1 <= px && x2 >= px && y1 <= py && y2 >= py){
return true;
}
}
}
return false;
}
ll solve(){
ll low = f[1] = 0, high = INF, ans = INF;
for(int i = 1; i < n; i++){
f[i + 1] = f[i] + l[i];
}
while(low <= high){
ll mid = (low + high) >> 1LL;
if(check(mid)){
high = (ans = mid) - 1;
}
else{
low = mid + 1;
}
}
return ans;
}
}
namespace sub678{
int pi[lim], pj[lim];
pair<ll, ll>overlap(pair<ll, ll>r1, pair<ll, ll>r2){
return make_pair(max(r1.first, r2.first), min(r1.second, r2.second));
}
bool check(ll k){
ll x1 = -INF, x2 = INF, y1 = -INF, y2 = INF, kc = k - c;
pair<int, int>max_plus = make_pair(0, 0), min_minus = make_pair(0, 0);
for(int ptj = 0, pti = 0; ptj < n; ptj++){
int j = pj[ptj];
while(pti < n){
int i = pi[pti];
if(f[j] + d[j] - f[i] + d[i] <= k){
break;
}
pti++;
if(max_plus.first == 0){
max_plus.first = min_minus.first = i;
}
else{
ll val = f[i] + d[i];
if(val >= f[max_plus.first] + d[max_plus.first]){
max_plus.second = max_plus.first;
max_plus.first = i;
}
else if(max_plus.second == 0 || val > f[max_plus.second] + d[max_plus.second]){
max_plus.second = i;
}
if((val = f[i] - d[i]) <= f[min_minus.first] - d[min_minus.first]){
min_minus.second = min_minus.first;
min_minus.first = i;
}
else if(min_minus.second == 0 || val < f[min_minus.second] - d[min_minus.second]){
min_minus.second = i;
}
}
}
if(pti > 0){
if(kc < 0){
return false;
}
int i = max_plus.first == j ? max_plus.second : max_plus.first;
if(i != 0){
ll max_plus = f[i] + d[i];
maximize(x1, max_plus + f[j] + d[j] - kc);
minimize(y2, f[j] - d[j] - max_plus + kc);
}
if((i = min_minus.first == j ? min_minus.second : min_minus.first) != 0){
ll min_minus = f[i] - d[i];
minimize(x2, min_minus + f[j] - d[j] + kc);
maximize(y1, f[j] + d[j] - min_minus - kc);
}
}
}
if(x1 > x2 || y1 > y2){
return false;
}
for(int j = 1, ix1 = n, ix2 = n, iy1 = 1, iy2 = 1; j <= n; j++){
while(ix1 > 0 && f[j] + f[ix1] >= x1){
ix1--;
}
while(ix2 > 0 && f[j] + f[ix2] > x2){
ix2--;
}
while(iy1 <= n && f[j] - f[iy1] >= y1){
iy1++;
}
while(iy2 <= n && f[j] - f[iy2] > y2){
iy2++;
}
pair<ll, ll>rall = overlap(overlap(make_pair(1, j - 1), make_pair(ix1 + 1, ix2)), overlap(make_pair(1, iy1 - 1), make_pair(iy2, j)));
if(rall.first <= rall.second){
return true;
}
}
return false;
}
ll solve(){
for(int i = f[1] = 0; i < n; i++){
pi[i] = pj[i] = i + 1;
}
for(int i = 1; i < n; i++){
f[i + 1] = f[i] + l[i];
}
sort(pi, pi + n, [&] (int i, int j){
return f[i] - d[i] < f[j] - d[j];
});
sort(pj, pj + n, [&] (int i, int j){
return f[i] + d[i] < f[j] + d[j];
});
ll low = *max_element(d + 1, d + n + 1), high = INF, ans = INF;
while(low <= high){
ll mid = (low + high) >> 1LL;
if(check(mid)){
high = (ans = mid) - 1;
}
else{
low = mid + 1;
}
}
return ans;
}
}
ll find_shortcut(int _n, vector<int>_l, vector<int>_d, int _c){
c = _c;
for(int i = n = _n; i > 0; i--){
l[i] = _l[i - 1];
d[i] = _d[i - 1];
}
if(n <= 100){
return sub12::solve();
}
if(n <= 500){
return sub34::solve();
}
if(n <= 3000){
return sub5::solve();
}
return sub678::solve();
}
