#include <bits/stdc++.h>
#ifndef ARTHUR_LOCAL
#include "shortcut.h"
#endif
using namespace std;
using ll = long long;
void merger(pair<int,int> &a, pair<int,int> b)
{
// cout << a.first << " " << a.second << endl;
int from = max(a.first,b.first);
int to = min(a.second,b.second);
if(from>=to) a = {-1,-1};
else a = make_pair(from,to);
}
ll find_shortcut(int n, vector<int> L, vector<int> D, int c)
{
vector<pair<int,int>> segs;
vector<pair<ll,int>> diams;
vector<ll> pref_sums(n+1);
for(int i=2; i<=n; i++)
{
pref_sums[i] = pref_sums[i-1] + ll(L[i-2]);
}
for(int i=1; i<=n; i++)
{
for(int j=i; j<=n; j++)
{
segs.push_back({i,j});
if(i==j)
{
diams.push_back({ll(D[i-1]),segs.size()-1});
}
else diams.push_back({pref_sums[j]-pref_sums[i]+ll(D[j-1]+D[i-1]),segs.size()-1});
}
}
sort(diams.rbegin(),diams.rend());
// for(auto d:diams)
// {
// cout << segs[d.second].first << " " << segs[d.second].second << endl;
// cout << d.first << endl;
// }
diams.push_back({0,0}); // should add a buffer for
pair<int,int> active = {1,n};
ll ans = diams[0].first;
for(int i=0; i<int(diams.size())-1; i++)
{
merger(active,segs[diams[i].second]);
if(active.first==-1) break;
ll savings = pref_sums[active.second]-pref_sums[active.first]-ll(c);
// cout << savings << endl;
ans = min(ans, max(diams[0].first - savings,diams[i+1].first));
}
return ans;
}
#ifdef ARTHUR_LOCAL
int main()
{
cout << find_shortcut(4, {10, 20, 20}, {0, 40, 0, 30}, 10) << endl;
}
#endif
