#include "shortcut.h"
#include <vector>
#include <algorithm>
using namespace std;
struct ei {
long long dis;
pair<int,int> range;
};
bool operator< (const ei &a, const ei &b) {
return a.dis>b.dis;
}
pair<int,int> comb(const pair<int,int> &a, const pair<int,int> &b) {
if (b.first>a.second) return {-1,-1};
return {max(a.first,b.first),min(a.second,b.second)};
}
long long find_shortcut(int n, vector<int> l, vector<int> d, int c)
{
vector<long long> qs(n,0);
for (int i=1;i<n;i++) {
qs[i]=l[i];
qs[i]+=qs[i-1];
}
vector<ei> tbl;
tbl.reserve(n*(n-1)/2);
long long ans=0;
long long mx=0;
for (int i=0;i<n;i++) {
for (int j=i+1;j<n;j++) {
tbl.push_back(ei{qs[j]-qs[i]+d[j]+d[i],{i,j}});
mx=max(mx,qs[j]-qs[i]+d[j]+d[i]);
}
}
ans=mx;
sort(tbl.begin(),tbl.end());
pair<int,int> cur={0,n-1};
long long curans;
long long red;
for (int i=0;i<(int)tbl.size();i++) {
cur=comb(cur,tbl[i].range);
if (cur.first==-1) break;
red=qs[cur.second]-qs[cur.first]-c;
if (red<=0) break;
if (i==(int)tbl.size()-1||tbl[i+1].dis!=tbl[i].dis) {
curans=mx-red;
if (i!=(int)tbl.size()-1) {
curans=max(curans,tbl[i+1].dis);
}
ans=min(ans,curans);
}
}
return ans;
}
