#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include "shortcut.h"
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
const int MAX_N = 3010;
// inf is big enough
const ll inf = 1ll << 59;
int n, C;
ll pf[MAX_N], suf[MAX_N], loc[MAX_N];
ll pfd[MAX_N], sufd[MAX_N];
ll dis(int i, int j) {
return abs(loc[i] - loc[j]);
}
vector<int> l, d;
void init() {
for (int i = 0;i+1 < n;++i) {
loc[i+1] = loc[i] + l[i];
}
{
pfd[0] = pf[0] = d[0];
for (int i = 1;i < n;++i) {
pf[i] = max(pf[i-1], d[i] - loc[i]);
pfd[i] = max(pfd[i-1], d[i] + loc[i] + pf[i-1]);
}
}
{
sufd[n-1] = suf[n-1] = d[n-1];
for (int i = n-2;i >= 0;--i) {
suf[i] = max(suf[i+1], d[i] - (loc[n-1] - loc[i]));
sufd[i] = max(sufd[i+1], d[i] + (loc[n-1] - loc[i]) + suf[i+1]);
}
}
}
ll cal(int a, int b) {
//if (C >= dis(a, b)) return inf - b;
ll C = min((ll)::C, dis(a, b));
ll ld = dis(0, a) + pf[a], rd = dis(b, n-1) + suf[b];
ll res = max({pfd[a], sufd[b],
ld + rd + C});
for (int i = a;i <= b;++i) {
// first to l, r
ll tol = min(dis(i, a), dis(i, b) + C),
tor = min(dis(i, b), dis(i, a) + C);
if (i > a) chmax(res, d[i] + tol + ld);
if (i < b) chmax(res, d[i] + tor + rd);
for (int j = i+1;j <= b;++j) {
ll dij = min(dis(i, j), C + dis(a, b) - dis(i, j));
chmax(res, d[i] + d[j] + dij);
}
}
//
// auto nxt = [&](int i) {
// return i < b ? i+1 : a;
// };
// auto gdis = [&](int i, int j) {
// return min(dis(i, j), dis(a, b) + C - dis(i, j));
// };
// // tor distance
// auto rdis = [&](int i, int j) {
// if (j < i) return dis(a, b) + C - dis(i, j);
// return dis(i, j);
// };
// for (int i = a, j = a;i <= b;++i) {
// deque<pair<ll,ll>> dq;
// while (nxt(j) != i && gdis(i, nxt(j)) == rdis(i, nxt(j))) {
// j = nxt(j);
// push_in(j);
// }
// while (dq.size() && dq[0].first <= i)
//
// }
//
DE(a, b, res);
return res;
}
long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c) {
::n = n;
::l = l;
::d = d;
C = c;
init();
ll res = pfd[n-1];
function<void(int,int,int,int)> dcop = [&](int l, int r, int sl, int sr) {
if (l > r) return;
int mid = l + r >> 1;
int bst = -1;
ll ans = inf;
for (int i = sl;i <= sr && i < mid;++i) {
if (chmin(ans, cal(i, mid)))
bst = i;
}
chmin(res, ans);
dcop(l, mid-1, sl, bst);
dcop(mid+1, r, bst, sr);
};
//dcop(0, n-1, 0, n-1);
for (int i = 0;i < n;++i) {
for (int j = i+1;j < n;++j)
chmin(res, cal(i, j));
}
return res;
}
