#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e5 + 5, INF = 1e18;
int n, c;
pair<int,int> a[maxn];
pair<int,int> calc(vector<pair<int,int>> vec) {
int sz = vec.size();
int sum = 0;
for (auto [L, D]:vec) sum += L;
int mid = 0, dist = 0;
while (dist + vec[mid].first <= sum - dist - vec[mid].first) {
dist += vec[mid].first;
mid++;
}
int mx = 0, mxi = 0;
dist = 0;
for (int i=1;i<=mid;i++) {
dist += vec[i-1].first;
if (vec[i].second + dist > mx) mxi = i, mx = vec[i].second + dist;
}
// cout << mx << " " << mxi << endl;
dist = 0;
for (int i=sz-1;i>mid;i--) {
dist += vec[i].first;
if (vec[i].second + dist > mx) mxi = i, mx = vec[i].second + dist;
}
// cout << mx << " " << mxi << endl;
// cout << "test\n";
// for (auto [x, y]:vec) cout << x << " " << y << endl;
// cout << "ret " << mx << " " << mxi << endl;
// cout << endl;
return {mx + vec[0].second, mxi};
}
int calc2(vector<pair<int,int>> vec) {
int sz = vec.size();
int ps[sz]; ps[0] = 0;
for (int i=1;i<sz;i++) ps[i] = ps[i-1] + vec[i-1].first;
int sum = ps[sz-1] + c;
int mx = 0;
for (int i=0;i<sz;i++) for (int j=i+1;j<sz;j++) {
int dist = ps[j] - ps[i];
if (sum - dist < dist) dist = sum - dist;
mx = max(dist + vec[i].second + vec[j].second, mx);
}
return mx;
}
int cnt(int l, int r) {
if (l==r) return INF;
int sz = r-l+1;
vector<pair<int,int>> cur;
int dist = 0, mx = 0;
int ps[n]; ps[0] = 0;
for (int i=1;i<n;i++) ps[i] = ps[i-1] + a[i-1].first;
for (int i=l;i>=0;i--) {
// if (i!=l) MX += a[i].first;
// lhs = max(a[i].second + MX, lhs);
// MX = max(a[i].second, MX);
mx = max(ps[l] - ps[i] + a[i].second, mx);
}
cur.push_back({a[l].first, mx});
for (int i=l+1;i<r;i++) cur.push_back({a[i].first, a[i].second});
dist = mx = 0;
for (int i=r;i<n;i++) {
// if (i!=r) MX += a[i-1].first;
// rhs = max(a[i].second + MX, rhs);
// MX = max(a[i].second, MX);
mx = max(ps[i] - ps[r] + a[i].second, mx);
}
cur.push_back({c, mx});
int lhs = 0;
for (int i=0;i<=l;i++) for (int j=i+1;j<=l;j++) lhs = max(ps[j]-ps[i] + a[i].second + a[j].second, lhs);
int rhs = 0;
for (int i=r;i<n;i++) for (int j=i+1;j<n;j++) rhs = max(ps[j]-ps[i] + a[i].second + a[j].second, rhs);
int both = 0;
for (int i=0;i<=l;i++) for (int j=r;j<n;j++) {
int dist = ps[j] - ps[i] - (ps[r] - ps[l]) + min(ps[r] - ps[l], c);
both = max(dist + a[i].second + a[j].second, both);
}
return max({calc2(cur), lhs, rhs, both});
// int start = calc(cur).second;
// vector<pair<int,int>> cur2;
// for (int i=0;i<sz;i++) cur2.push_back(cur[(i+start)%sz]);
// int val = calc(cur2).first;
}
long long find_shortcut(int32_t N, vector<int32_t> L, vector<int32_t> d, int32_t C) {
if (N >= 1000) return 69420;
n = N, c = C;
for (int i=0;i<n-1;i++) a[i] = {L[i], d[i]};
a[n-1] = {-1, d[n-1]};
int ps[n]; ps[0] = 0;
for (int i=1;i<n;i++) ps[i] = ps[i-1] + a[i-1].first;
int ans = 0;
for (int i=0;i<n;i++) for (int j=i+1;j<n;j++) ans = max(ps[j]-ps[i] + a[i].second + a[j].second, ans);
for (int i=0;i<n;i++) for (int j=i+1;j<n;j++) ans = min(cnt(i, j), ans);
return ans;
for (int i=0;i<n-1;i++) {
// for (int j=i+1;j<n;j++) cout << cnt(i, j) << " ";
// cout << endl;
int l = i, r = n-1;
while (l<r) {
int mid = (l+r)/2;
if (cnt(i, mid) < cnt(i, mid+1)) r = mid;
else l = mid+1;
}
ans = min(cnt(i, l), ans);
}
return ans;
}
