#include "shortcut.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n;
vector<vector<ll>> st;
void update(int pos, ll val, int t, int node=1, int tl=0, int tr=n-1){
if (tl == tr){
st[t][node] = val;
return;
}
int tm = (tl+tr)/2;
if (pos <= tm) update(pos, val, t, node*2, tl, tm);
else update(pos, val, t, node*2+1, tm+1, tr);
st[t][node] = max(st[t][node*2], st[t][node*2+1]);
}
ll query(int l, int r, int t, int node=1, int tl=0, int tr=n-1){
if (l > r) return -(1ll<<50);
if (l <= tl && tr <= r) return st[t][node];
int tm = (tl+tr)/2;
ll res = -(1ll<<50);
if (l <= tm) res = max(res, query(l, r, t, node*2, tl, tm));
if (tm+1 <= r) res = max(res, query(l, r, t, node*2+1, tm+1, tr));
return res;
}
ll find_shortcut(int n, vector<int> l, vector<int> d, int c){
::n = n;
vector<ll> ps(n, 0);
for (int i=0; i<n-1; i++) ps[i+1] = ps[i]+l[i];
st.resize(2, vector<ll>(4*n, -(1ll<<50)));
for (int i=0; i<n; i++){
update(i, ps[i]+d[i], 0);
update(i, ps[n-1]-ps[i]+d[i], 1);
}
ll bsf = (1ll<<50);
for (int i=0; i<n; i++){
for (int j=i+1; j<n; j++){
ll cur = 0;
for (int x=0; x<n-1; x++){
int lo = x, hi = n;
while (lo != hi-1){
int m = (lo+hi)/2;
if (ps[m]-ps[x] > abs(ps[x]-ps[i])+abs(ps[m]-ps[j])+c) hi = m;
else lo = m;
}
//cout << i << " " << j << " " << x << " " << hi << endl;
ll d1 = d[x]+query(x+1, hi-1, 0)-ps[x];
ll d2 = d[x]+abs(ps[x]-ps[i])+c+query(hi, j, 1)+ps[j]-ps[n-1];
ll d3 = d[x]+abs(ps[x]-ps[i])+c+query(max(j, hi), n-1, 0)-ps[j];
//cout << d1 << " " << d2 << " " << d3 << endl;
cur = max(cur, max(d1, max(d2, d3)));
}
//cout << i << " " << j << " " << cur << endl;
bsf = min(bsf, cur);
}
}
return bsf;
}
