#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
#ifdef dremix
#define p(x) cerr<<#x<<" = "<<x<<endl;
#define p2(x,y) cerr<<#x<<" , "<<#y<<" = "<<x<<" , "<<y<<endl;
#define pp(x) cerr<<#x<<" = ("<<x.F<<" - "<<x.S<<")"<<endl;
#define pv(x) cerr<<#x<<" = {";for(auto u : x)cerr<<u<<", ";cerr<<"}"<<endl;
#define ppv(x) cerr<<#x<<" = {";for(auto u : x)cerr<<u.F<<"-"<<u.S<<", ";cerr<<"}"<<endl;
#else
#define p(x) {}
#define p2(x,y) {}
#define pp(x) {}
#define pv(x) {}
#define ppv(x) {}
#endif
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
const int N = 1e6+5;
const int MOD = 1e9+7;
const ll INF = 1e18+5;
long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c)
{
ll dist[n][n] = {};
l.push_back(0);
int i,j,k;
ll maxr[n] = {}, maxl[n] = {};
for(i=0;i<n;i++){
ll sum = d[i];
//dist[i][i] = sum;
//maxcol[i] = max(maxcol[i],sum);
for(j=i+1;j<n;j++){
sum += l[j-1];
dist[i][j] = sum + d[j];
maxr[j] = max(maxr[j],dist[i][j]);
maxl[i] = max(maxl[i],dist[i][j]);
}
}
ll suffl[n], box[n][n];
suffl[n-1] = maxl[n-1];
box[0][n-1] = dist[0][n-1];
for(i=n-2;i>=0;i--){
suffl[i] = max(suffl[i+1],maxl[i]);
box[0][i] = max(box[0][i+1],dist[0][i]);
}
for(i=1;i<n;i++){
ll maxi = 0;
for(j=n-1;j>=0;j--){
maxi = max(maxi,dist[i][j]);
box[i][j] = max(box[i-1][j],maxi);
}
}
ll ans = INF;
ll beg = 0, fin;
ll mids[n] = {};
ll keep[n][n] = {};
for(i=0;i<n;i++){
beg = max(beg,maxr[i]);
for(j=i+1;j<n;j++){
fin = maxl[j];
ll win = max(0ll,dist[i][j]-d[i]-d[j] - c);
ll res = max({beg,fin,box[i][j]-win});
// todo: beg goes to mid | mid goes to mid | mid goes to fin
// beg goes to mid
ll winbeg = win;
for(k=j-1;k>i;k--){
winbeg -= l[k]*2;
winbeg = max(0ll,winbeg);
res = max(res,mids[k]-winbeg);
}
ll winmid = win;
// mid goes to mid
for(k=i+1;k<j;k++){
for(int o=k+1;o<j;o++){
res = max(res,min(dist[k][o],dist[i][k]+dist[o][j]-d[i]-d[j]+c));
}
}
keep[i][j] = res;
mids[j] = max(mids[j],dist[i][j]);
}
}
ll mide[n]= {};
//ll ans = 0;
for(j=n-1;j>=0;j--){
//beg = max(beg,maxr[i]);
for(i=j-1;i>=0;i--){
//fin = maxl[j];
ll win = max(0ll,dist[i][j]-d[i]-d[j] - c);
ll res = keep[i][j];
// todo: beg goes to mid | mid goes to mid | mid goes to fin
// beg goes to mid
ll winbeg = win;
for(k=i+1;k<j;k++){
winbeg -= l[k-1]*2;
winbeg = max(0ll,winbeg);
res = max(res,mide[k]-winbeg);
}
/*
ll winmid = win;
// mid goes to mid
for(k=i+1;k<j;k++){
for(int o=k+1;o<j;o++){
res = max(res,min(dist[k][o],dist[i][k]+dist[o][j]-d[i]-d[j]+c));
}
}
*/
if(res == 100){
p2(i,j)
p2(keep[i][j],res)
}
mide[i] = max(mide[i],dist[i][j]);
ans = min(ans,res);
}
}
return ans;
}
