// ~ Be Name Khoda ~ //
#include "shortcut.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define fi first
#define se second
const int maxn = 1e6 + 10;
const int maxn5 = 3e3 + 10;
const int maxnt = 1.2e6 + 10;
const int maxn3 = 1e3 + 10;
const ll mod = 1e9 + 7;
const int lg = 20;
const ll inf = 1e18;
int n;
ll c;
vector <ll> d;
ll ps[maxn5], ps2[maxn5];
vector <ll> av[maxn5][2];
ll dis(int a, int b){
if(a > b)
swap(a, b);
return ps[b] - ps[a];
}
bool check(ll lim){
for(int i = 0; i < n; i++){
int l = i + 1, r = n;
bool re = true;
for(int j = 0; j < n && re; j++) for(int k = j + 1; k < n && re; k++) if(dis(j, k) + d[j] + d[k] > lim){
ll dis1 = dis(i, j);
ll need = lim - c - d[j] - d[k] - dis1;
if(need < 0)
re = false;
int ptl = k - (upper_bound(all(av[k][0]), need) - av[k][0].begin() - 1);
int ptr = k + (upper_bound(all(av[k][1]), need) - av[k][1].begin() - 1);
l = max(l, ptl);
r = min(r, ptr);
//cout << lim << ' ' << i << ' ' << j << ' ' << k << ' ' << l << ' ' << r << endl;
if(l > r)
re = false;
}
if(re)
return true;
}
return false;
}
long long find_shortcut(int N, std::vector<int> l, std::vector<int> D, int C)
{
n = N;
c = C;
for(auto u : D)
d.pb(u);
ps[0] = 0;
for(int i = 1; i < n; i++)
ps[i] = ps[i - 1] + l[i - 1];
for(int i = 0; i < n; i++){
for(int j = i; j >= 0; j--)
av[i][0].pb(dis(i, j));
for(int j = i; j < n; j++)
av[i][1].pb(dis(i, j));
}
ll lo = -1, hi = mod * (n + 3);
while(hi - lo > 1){
ll mid = (lo + hi) >> 1;
if(check(mid))
hi = mid;
else
lo = mid;
}
return hi;
}
