#include <bits/stdc++.h>
#include "shortcut.h"
using namespace std;
const long long MAX = 1'000'000'000'000'000'000;
const int N = 500 + 10;
long long pref[N];
inline long long dist(int i, int j) {
if (i > j) swap(i, j);
return pref[j] - pref[i];
}
long long find_shortcut(int n, vector<int> l, vector<int> d, int c) {
for (int i = 1; i < n; ++i) pref[i] = pref[i - 1] + l[i - 1];
long long answer = MAX;
for (int st = 0; st < n; ++st) {
for (int ed = st + 1; ed < n; ++ed) {
long long ret = -MAX;
long long ma = -MAX;
deque<int> q;
for (int i = 0, it = 0; i < n; ++i) {
for (; it < i && dist(i, ed) + c + dist(st, it) <= dist(it, i); ++it) {
ma = max(ma, c + dist(st, it) + d[it]);
}
while (q.size() && q.front() < it) q.pop_front();
ret = max(ret, ma + dist(i, ed) + d[i]);
if (q.size()) ret = max(ret, dist(i, q.front()) + d[i] + d[q.front()]);
while (q.size() && dist(i, i) + d[i] >= dist(i, q.back()) + d[q.back()]) q.pop_back();
q.push_back(i);
}
ma = -MAX;
for (int i = n - 1, it = n - 1; i >= 0; --i) {
for (; it > i && dist(i, st) + c + dist(ed, it) <= dist(i, it); --it) {
ma = max(ma, c + dist(ed, it) + d[it]);
}
ret = max(ret, ma + dist(i, st) + d[i]);
}
answer = min(answer, ret);
}
}
return answer;
}
