#include "shortcut.h"
#include <bits/stdc++.h>
#define ll long long
// #define int ll
#define pii pair<int,int>
#define F first
#define S second
#define sz(s) (int)s.size()
#define in insert
#define pb push_back
#define all(v) v.begin(),v.end()
#define mem(a,i) memset(a,i,sizeof(a))
using namespace std;
const int MAX=2e5+10;
const ll inf=1e18;
int n;
ll c;
ll pin[MAX];
ll pin1[MAX];
ll get(int l,int r,vector<int> &d){
ll ans=0;
// cout<<l<<" "<<r<<"\n";
{
ll mx1=-inf;
for(int i=0;i<=l;i++){
ans=max(ans,pin[i]+d[i]+mx1);
// cout<<pin[i]+d[i]+mx1<<"\n";
mx1=max(mx1,d[i]-pin[i]);
}
}
{
ll mx1=-inf;
for(int i=0;i<l;i++)mx1=max(mx1,pin[l]-pin[i]+d[i]);
for(int i=l;i<=r;i++){
// cout<<mx1+min(pin[i]-pin[l],pin[r]-pin[i]+c)+d[i]<<"\n";
ans=max(ans,mx1+min(pin[i]-pin[l],pin[r]-pin[i]+c)+d[i]);
}
}
{
ll mx1=-inf;
for(int i=0;i<=l;i++){
mx1=max(mx1,pin[l]-pin[i]+d[i]);
}
for(int i=r;i<n;i++){
// cout<<pin[i]-pin[r]+min(c,pin[r]-pin[l])+mx1+d[i]<<"\n";
ans=max(ans,pin[i]-pin[r]+min(c,pin[r]-pin[l])+mx1+d[i]);
}
}
// cout<<"!! "<<ans<<"\n";
return ans;
}
ll calc(int l,int r,vector<int> &d){
ll ans=get(l,r,d);
reverse(all(d));
for(int i=0;i<n;i++)swap(pin[i],pin1[i]);
ans=max(ans,get(n-r-1,n-l-1,d));
reverse(all(d));
for(int i=0;i<n;i++)swap(pin[i],pin1[i]);
return ans;
}
ll calcmid(int l,int r,vector<int> &d){
ll ans=0;
for(int i=l;i<=r;i++){
for(int j=i+1;j<=r;j++){
ll dist=pin[j]-pin[i];
ans=max(ans,min(dist,pin[r]-pin[l]+c-dist)+d[i]+d[j]);
}
}
return ans;
}
long long find_shortcut(int N, vector<int> l, vector<int> d, int C){
n=N;
c=C;
ll ans=inf;
for(int i=1;i<n;i++){
pin[i]=pin[i-1]+l[i-1];
}
for(int i=1;i<n;i++){
pin1[i]=pin1[i-1]+l[n-1-i];
}
for(int i=0;i<n;i++){
ll mid=-inf,mid1=-inf;
for(int j=i+1;j<n;j++){
ll x=calc(i,j,d);
ans=min(ans,max(x,calcmid(i,j,d)));
// cout<<x<<" "<<calcmid(i,j,d)<<"\n";
}
}
return ans;
}
