#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
long long N, C, D[509][509], A[509], B[509], dp[509];
long long solve(int cl, int cr) {
for (int i = 0; i < N; i++) dp[i] = D[0][i];
if (dp[cl] > dp[cr] + C) { dp[cl] = dp[cr] + C; }
if (dp[cr] > dp[cl] + C) { dp[cr] = dp[cl] + C; }
for (int i = 0; i < N - 1; i++) dp[i + 1] = min(dp[i + 1], dp[i] + D[i][i + 1]);
for (int i = N - 2; i >= 0; i--) dp[i] = min(dp[i], dp[i + 1] + D[i][i + 1]);
pair<long long, int> m1 = make_pair(-1LL, -1);
for (int i = 0; i < N; i++) m1 = max(m1, make_pair(dp[i] + B[i], i));
int root = m1.second;
for (int i = 0; i < N; i++) dp[i] = D[root][i];
if (dp[cl] > dp[cr] + C) { dp[cl] = dp[cr] + C; }
if (dp[cr] > dp[cl] + C) { dp[cr] = dp[cl] + C; }
for (int i = 0; i < N - 1; i++) dp[i + 1] = min(dp[i + 1], dp[i] + D[i][i + 1]);
for (int i = N - 2; i >= 0; i--) dp[i] = min(dp[i], dp[i + 1] + D[i][i + 1]);
pair<long long, int> m2 = make_pair(B[root], root);
for (int i = 0; i < N; i++) { if (i == root) continue; m2 = max(m2, make_pair(dp[i] + B[i] + B[root], i)); }
return m2.first;
}
long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c) {
N = n; C = c;
for (int i = 0; i < N; i++) { if (i < N - 1) A[i] = l[i]; B[i] = d[i]; }
for (int i = 0; i < N; i++) {
long long S = 0;
for (int j = i + 1; j < N; j++) {
S += 1LL * l[j - 1];
D[i][j] = S; D[j][i] = S;
}
}
long long ans = (1LL << 60);
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) ans = min(ans, solve(i, j));
}
return ans;
}
