#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> dist;
long long t(long long l, long long r) {
if (l > r) {return 0; swap(l, r);}
return dist[r] - dist[l];
}
long long diam(long long l, long long r) {
// build shortcut l -> r
long long ans1 = 0, ans2 = 0, ans3 = 0, ans4 = 0, ans5 = 0;
vector<vector<long long>> maxR(n, vector<long long>(n)), maxBruh(n, vector<long long>(n));
for (long long i = 0; i < n; i++) {
maxR[i][i] = d[i] + dist[i];
for (long long j = i + 1; j < n; j++) {
maxR[i][j] = max(maxR[i][j - 1], d[j] + dist[j]);
}
}
for (long long i = 0; i < n; i++) {
maxBruh[i][i] = d[i] - dist[i];
for (long long j = i + 1; j < n; j++) {
maxBruh[i][j] = max(maxBruh[i][j - 1], d[j] - dist[j]);
}
}
for (int i = 0; i < n; i++) {
for (int j = i - 1; j >= 0; j--) {
maxBruh[i][j] = maxR[i][j] = -1e18;
}
}
// both on left
long long mxL = 0;
long long mx = 0;
for (long long i = 0; i <= l; i++) {
ans1 = max(ans1, dist[i] + d[i] + mx);
mx = max(mx, d[i] - dist[i]);
}
mxL = mx;
// both on right
long long mxR = 0;
mx = -dist[r];
for (long long i = r; i < n; i++) {
ans2 = max(ans2, dist[i] + d[i] + mx);
// cout << i << " ans2 " << ans2 << '\n';
mx = max(mx, d[i] - dist[i]);
mxR = max(mxR, dist[i] + d[i]);
}
// I-out-J-in
for (long long i = l; i <= r; i++) {
long long cost = min(t(l, i), t(i, r) + c) + d[i];
// worst guy <= l? mxL
// cout << i << " " << dist[l] << " + " << mxL << " + " << cost << '\n';
ans3 = max(ans3, dist[l] + mxL + cost);
}
// I-in-J-out
for (long long i = l; i <= r; i++) {
long long cost = min(t(i, r), t(i, l) + c) + d[i];
// worst guy >= r?
// cout << i << " ans4 " << cost << " + " << mxR << " - " << dist[r] << '\n';
ans4 = max(ans4, cost + mxR - dist[r]);
}
// both in :C
long long ptr = l;
for (long long i = l; i < r-1; i++) {
while (t(i, ptr) < t(l, r) - t(i, ptr) + c) {
if (ptr > r) break; // maybe = too?
ptr++;
}
// cout << i << " starts wrap at " << ptr << '\n';
// cout << "notwrap: " << d[i] + maxR[i + 1][ptr - 1] - dist[i] << '\n';
// if (ptr <= r) cout << d[i] << " + " << maxR[i + 1][ptr - 1] << " - " << dist[i] << '\n';
// if (ptr <= r) cout << "wrap: " << dist[i] + d[i] + dist[r] - dist[l] + maxBruh[ptr][r] + c << '\n';
// at ptr i do a wrap around
if (ptr <= r) ans5 = max(ans5, d[i] + maxR[i + 1][ptr - 1] - dist[i]);
if (ptr <= r) ans5 = max(ans5, dist[i] + d[i] + dist[r] - dist[l] + maxBruh[ptr][r] + c);
}
// wide
int bridge = min(dist[r] - dist[l], c);
long long ans6 = bridge + (maxBruh[0][l] + dist[l]) + (maxR[r][n - 1] - dist[r]);
// cout << "ans6 " << bridge << " + " << (maxBruh[0][l] + dist[l]) << " + " << (maxR[r][n - 1] - dist[r]) << "\n";
// cout << ans1 << " " << ans2 << " " << ans3 << " " << ans4 << " " << ans5 << " " << ans6 << "\n";
return max({ans1, ans2, ans3, ans4, ans5, ans6});
}
long long find_shortcut(int n_f, vector<int> l_f, vector<int> d_f, int c_f)
{
n = n_f; c = c_f;
for (auto &x : l_f) l.push_back(x);
for (auto &x : d_f) d.push_back(x);
dist.resize(n);
for (long long i = 1; i < n; i++) {
dist[i] = dist[i - 1] + l_f[i - 1];
}
if (n == 2) {
assert(dist[1] - dist[0] >= c);
}
// int ans = diam(2, 7);
long long ans = 1e18;
for (long long i = 0; i < n; i++) {
for (long long j = i+1; j < n; j++) {
// build i, j
long long x = diam(i, j);
ans = min(ans, x);
// cout << x << " ";
}
// cout << '\n';
}
return ans;
}
