#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
// #define long long long long
long long n, c;
vector<long long> l, d;
vector<long long> x;
int in(long long x, pair<long long, long long> p) {
return ((x >= p.first) && (x <= p.second));
}
bool ok(long long v) {
pair<long long, long long> pb = {-1e18, 1e18}, sb = {-1e18, 1e18}; // y - z
for (int j = 1; j < n; j++) {
for (int i = j - 1; i >= 0; i--) {
if (d[i] + d[j] + x[j] - x[i] <= v) continue;
if (c > v) return false;
pb.first = max(pb.first, x[j] + x[i] - v + c + d[i] + d[j]);
pb.second = min(pb.second, v - c + x[i] + x[j] - d[i] - d[j]);
sb.first = max(sb.first, -(v - c) + x[i] - x[j] + d[i] + d[j]);
sb.second = min(sb.second, v - c + x[i] - x[j] - d[i] - d[j]);
}
}
for (int y = 0; y < n; y++) {
for (int z = y + 1; z < n; z++) {
if (in(x[y] - x[z], sb) && in(x[y] + x[z], pb)) return true;
}
}
return false;
}
long long find_shortcut(int n_f, vector<int> l_f, vector<int> d_f, int c_f)
{
n = n_f; c = c_f;
l.resize(n); d.resize(n); x.resize(n);
for (int i = 0; i < n; i++) {l[i] = l_f[i]; d[i] = d_f[i];}
x[0] = 0; for (int i = 1; i < n; i++) x[i] = x[i - 1] + l[i - 1];
long long lo = 0; long long hi = 1e18;
while (hi > lo + 1) {
long long mid = (lo + hi) / 2;
if (ok(mid)) hi = mid;
else lo = mid;
}
return hi;
}
