#include "shortcut.h"
#include <algorithm>
using namespace std;
typedef long long llong;
int n, c;
vector<llong> dist;
vector<int> etc;
vector<pair<llong, int>> ad, sb;
bool check(llong m) {
llong fs = -1ll, se = -1ll;
int fsi = -1, sei = -1, p, q;
llong lad = -1e18, gad = 1e18, lsb = -1e18, gsb = 1e18;
for (int i = 0, j = 0; i < n; ++i) {
while (j < n && sb[j].first + m < ad[i].first) {
p = sb[j].second;
llong mx = dist[p] + etc[p];
if (fs < mx) {
sei = fsi;
fsi = p;
se = fs;
fs = mx;
}
else if (se < mx) sei = p, se = mx;
++j;
}
p = ad[i].second;
if (p == sb[0].second && j == 1 || j == 0) continue;
llong adi = (p == fsi ? se : fs);
llong sbi = (p == sb[0].second ? sb[1].first : sb[0].first);
llong adj = dist[p] + etc[p];
llong sbj = dist[p] - etc[p];
lsb = max(lsb, adi - sbj - m + c);
gsb = min(gsb, sbi - adj + m - c);
lad = max(lad, adi + adj - m + c);
gad = min(gad, sbi + sbj + m - c);
}
llong gpos, lpos;
p = 0, q = n - 1;
for (int i = 0; i < n; ++i) {
gpos = min(dist[i] - lsb, gad - dist[i]);
lpos = max(dist[i] - gsb, lad - dist[i]);
while (p > 0 && dist[p - 1] >= lpos) --p;
while (p < n && dist[p] < lpos) ++p;
while (q >= 0 && dist[q] > gpos) --q;
while (q < n - 1 && dist[q + 1] <= gpos) ++q;
if (p <= q) return true;
}
return false;
}
long long find_shortcut(int N, std::vector<int> l, std::vector<int> d, int C) {
n = N; c = C;
dist.resize(n);
llong sum = 0ll;
for (int i = 1; i < n; ++i) {
sum += l[i - 1];
dist[i] = sum;
}
etc = d;
llong ld = 0ll, e = 0ll;
int fs = 0, se = 0;
for (int i = 0; i < n; ++i) {
ad.push_back({ dist[i] + etc[i], i });
sb.push_back({ dist[i] - etc[i], i });
e = max(e, ld + etc[i]);
if (fs < etc[i]) {
se = fs;
fs = etc[i];
}
else if (se < etc[i]) {
se = etc[i];
}
if (i < n - 1)
ld = max(ld, (llong)etc[i]) + l[i];
}
sort(ad.begin(), ad.end());
sort(sb.begin(), sb.end());
llong s = fs + se;
while (s < e) {
llong m = (s + e) / 2;
if (check(m)) e = m;
else s = m + 1ll;
}
return s;
}
