#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sep ' '
#define debug(x) cerr << #x << ": " << x << endl;
const ll MAXN = 1e6 + 10;
int n;
ll L[MAXN], ps[MAXN], D[MAXN], XT[MAXN], XS[MAXN], c;
inline ll dist(int i, int j) {
if (i > j) swap(i, j);
return ps[j] - ps[i];
}
inline ll solve(int l, int r) {
ll ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
ans = max(ans, min(dist(i, j), dist(i, l) + dist(r, j) + c)+ D[i] + D[j]);
}
}
return ans;
}
ll find_shortcut(int n_, vector<int> l_, vector<int> d_, int c_) {
n = n_;
c = c_;
for (int i = 1; i <= n; i++) {
L[i] = l_[i - 1];
D[i] = d_[i - 1];
if (i < n) ps[i + 1] = ps[i] + L[i];
XS[i] = D[i] - ps[i];
XT[i] = D[i] + ps[i];
}
ll ans = solve(1, 1);
for (int l = 1; l <= n; l++)
for (int r = l + 1; r <= n; r++)
ans = min(ans, solve(l, r));
return ans;
}
