#include "wiring.h"
#include <bits/stdc++.h>
#include <climits>
#include <queue>
using namespace std;
using ll = long long;
long long min_total_length(std::vector<int> r, std::vector<int> b) {
int n = r.size()+b.size();
//vector<ll> dp(n, -1);
vector<pair<int, bool>> vec(n);
int ii = 0;
for(int j = 0; ii+j<n; ){
if(ii==r.size()){
vec[ii+j] = {b[j], 1}; j++;
}
else if(j == b.size()){
vec[ii+j] = {r[ii], 0}; ii++;
}
else if(b[j] < r[ii]){
vec[ii+j] = {b[j], 1};
j++;
}
else{
vec[ii+j] = {r[ii], 0};
ii++;
}
}
vector<vector<int>> seq;
vector<vector<ll>> dp;
for(int i = 0; i<n; i++){
seq.push_back({vec[i].first});
dp.push_back({});
while(i+1<n && vec[i].second == vec[i+1].second){
seq.back().push_back(vec[i+1].first);
i++;
}
dp.back().resize(seq.back().size()+1, -1);
}
dp[0][0] = 0;
for(int i: seq[0]) dp[0][0] += seq[0].back()-i;
for(int i = 1; i<seq.size()-1; i++){
dp[i][0] = dp[i-1].back();
ll delta = seq[i][0]-seq[i-1].back();
deque<array<ll, 2>> q;
auto c = [&](array<ll, 2> arr, ll idx){
return arr[0]+max(arr[1], idx)*delta;
};
for(int j = seq[i-1].size()-1; j>=0; j--){
if(dp[i-1][j] == -1) continue;
array<ll, 2> nw = {dp[i-1][j], (ll)seq[i-1].size()-j};
ll cost = c(nw, 1);
while(q.size() && cost <= c(q.back(), 1)) q.pop_back();
q.push_back(nw);
}
ll sm = 0;
for(int j = 1; j<dp[i].size(); j++){
while(q.size() > 1 && c(q[0], j) >= c(q[1], j)) q.pop_front();
sm += seq[i][j-1]-seq[i][0];
dp[i][j] = c(q[0], j)+sm;
}
sm = 0;
for(int j =dp[i].size()-2; j>=0; j--){
if(dp[i][j] != -1) dp[i][j] += sm;
if(j> 0) sm += seq[i].back()-seq[i][j-1];
}
int cc;
}
ll sol = LONG_LONG_MAX;
int szl = seq.back().size();
int last = dp.size()-2;
ll delta = seq.back()[0]-seq[last].back();
auto c2 = [&](array<ll, 2> arr, ll idx){
return arr[0]+max(arr[1], idx)*delta;
};
for(int i = 0; i<dp[last].size()-1; i++){
sol = min(sol, c2({dp[last][i], (ll)seq[last].size()-i}, szl));
}
for(int i = seq.back().size()-1; i>0; i--){
sol += seq.back()[i]-seq.back()[0];
}
return sol;
}
