#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 20;
const long long inf = 1e15L + 20;
long long pos[maxn];
int depth[maxn];
int n, c;
bool check(long long lim) {
long long sum_lt = -inf;
long long sum_rt = inf;
long long diff_lt = -inf;
long long diff_rt = inf;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (j != i && pos[j] - pos[i] + depth[i] + depth[j] > lim) {
sum_lt = max(sum_lt, (pos[j] + depth[j]) + (pos[i] + depth[i]) - (lim - c));
sum_rt = min(sum_rt, (pos[j] - depth[j]) + (pos[i] - depth[i]) + (lim - c));
diff_lt = max(diff_lt, (-pos[j] + depth[j] + (pos[i] + depth[i]) - (lim - c)));
diff_rt = min(diff_rt, (-pos[j] - depth[j]) + (pos[i] - depth[i]) + (lim - c));
}
}
}
swap(diff_lt, diff_rt);
diff_lt = -diff_lt;
diff_rt = -diff_rt;
if (sum_lt > sum_rt || diff_lt > diff_rt) {
return false;
}
int lt1 = n;
int lt2 = 1;
for (int i = 1; i <= n; i++) {
while (lt1 > 1 && pos[i] + pos[lt1 - 1] >= sum_lt) {
lt1--;
}
while (lt2 <= n && pos[lt2] < pos[i] - diff_rt) {
lt2++;
}
int lt = max(lt1, lt2);
if (lt < i && pos[lt] <= sum_rt - pos[i] && pos[lt] <= pos[i] - diff_lt) {
return true;
}
}
return false;
}
long long find_shortcut(int _n, vector<int> len, vector<int> _depth, int _c) {
n = _n;
c = _c;
pos[1] = 0;
for (int i = 2; i <= n; i++) {
pos[i] = pos[i - 1] + len[i - 2];
}
for (int i = 1; i <= n; i++) {
depth[i] = _depth[i - 1];
}
long long lt = 0;
long long rt = inf;
long long res = -1;
while (lt <= rt) {
long long mt = (lt + rt) / 2;
if (check(mt)) {
res = mt;
rt = mt - 1;
}
else {
lt = mt + 1;
}
}
return res;
}
