#include "shortcut.h"
using namespace std;
#include <vector>
#include <iostream>
long long inf=1e17;
long long spar[100005];
long long atarna[100005];
long long pref[100005];
long long suff[100005];
int n;
long long dist(int a,int b,int c,int d,int add)
{
long long minim=inf;
minim=min(minim,spar[b]-spar[a]);
minim=min(minim,abs(spar[b]-spar[d])+abs(spar[a]-spar[c])+add);
return minim;
}
pair<long long,int>evalcamij(int pos,int tres,int x,int y,int c)
{
long long maxim=-inf,dir=-1,max2=-inf;
for(int i=pos+1;i<=tres;i++)
{
maxim=max(maxim,dist(pos,i,x,y,c)+atarna[i]);
}
for(int i=tres+1;i<=n;i++)
{
long long calc=dist(pos,i,x,y,c)+atarna[i];
if(calc>maxim)
{
dir=1;
maxim=calc;
}
}
for(int i=1;i<=pos;i++)
{
max2=max(max2,dist(i,pos,x,y,c)+atarna[i]);
}
return make_pair(max2+maxim,dir);
}
vector<int>vec;
long long evalciclu(int m1,int m2,int c)
{
long long maxim=0;
for(int i=0;i<vec.size();i++)
{
for(int j=i+1;j<vec.size();j++)
{
maxim=max(maxim,dist(vec[i],vec[j],m1,m2,c)+atarna[vec[i]]+atarna[vec[j]]);
}
}
return maxim;
}
pair<long long,long long>eval(int i,int j,int c)
{
vec.clear();
long long worst=0,dir=1;
if(c>spar[j]-spar[i])
{
return {inf,1};
}
worst=pref[i];
if(suff[j]>=worst)
{
worst=suff[j];
dir=1;
}
long long ciclelenght=spar[j]-spar[i]+c;
for(int c1=i;c1<=j;c1++)
{
//vec.push_back(spar[c1]-spar[c1-1]);
vec.push_back(c1);
}
//vec.push_back(c);
long long rezciclu=evalciclu(i,j,c);
if(rezciclu>worst)
{
worst=rezciclu;
dir=-1;
}
pair<long long,int> ev1=evalcamij(i,j,i,j,c);
if(ev1.first>=worst)
{
worst=ev1.first;
dir=ev1.second;
}
ev1=evalcamij(j,j,i,j,c);
if(ev1.first>=worst)
{
worst=ev1.first;
dir=1;
}
return make_pair(worst,dir);
}
long long find_shortcut(int m, std::vector<int> l, std::vector<int> d, int c)
{
n=m;
for(int i=2; i<=n; i++)
{
spar[i]=spar[i-1]+l[i-2];
}
for(int i=0;i<n;i++)
{
atarna[i+1]=d[i];
}
long long best=0;
for(int z=1; z<=n; z++)
{
for(int z2=z+1; z2<=n; z2++)
{
best=max(best,spar[z2]-spar[z]+d[z-1]+d[z2-1]);
}
}
for(int i=1;i<=n;i++)
{
pref[i]=pref[i-1];
for(int j=1;j<i;j++)
{
pref[i]=max(pref[i],spar[i]-spar[j]+atarna[i]+atarna[j]);
}
}
for(int i=n;i>=1;i--)
{
suff[i]=suff[i-1];
for(int j=n;j>i;j--)
{
suff[i]=max(suff[i],spar[j]-spar[i]+atarna[i]+atarna[j]);
}
}
for(int i=1; i<=n; i++)
{
int st=i+1,dr=n;
while(st<=dr)
{
int mij=(st+dr)/2;
pair<long long,long long>rez=eval(i,mij,c);
if(rez.second==1)
{
st=mij+1;
}
else
{
dr=mij-1;
}
best=min(best,rez.first);
}
}
return best;
}
