#include <bits/stdc++.h>
#include "wiring.h"
using ll = long long;
using namespace std;
const ll INF = 1e18;
struct MinQueue{
deque<pair<ll, int>> q;
int l = 0, r = 0;
ll min(){
if(q.empty()) return INF;
return q.front().first;
}
void push(ll x){
while(!q.empty() && q.back().first > x) q.pop_back();
q.push_back({x, l++});
}
bool empty(){ return q.empty(); }
void pop(){ if(!q.empty() && q.front().second == r++) q.pop_front(); }
};
ll min_total_length(vector<int> R, vector<int> B){
vector<pair<int, int>> a;
a.push_back({-1, -1});
for(auto x : R) a.push_back({x, 0});
for(auto x : B) a.push_back({x, 1});
sort(a.begin(), a.end());
int n = (int) a.size() - 1;
vector<int> pre(n + 1);
vector<ll> pref(n + 1, 0), dp(n + 1, INF);
for(int i=1; i<=n; i++) pre[i] = (a[i].second == a[i - 1].second ? pre[i - 1] : i - 1);
for(int i=1; i<=n; i++) pref[i] = pref[i - 1] + a[i].first;
MinQueue q;
int l = -1, r = -1, sz = 0;
ll min_right = INF, global_min = INF;
dp[0] = 0;
for(int i=1; i<=n; i++){
if(!pre[i]) continue;
if(pre[i] == i - 1){
while(!q.empty()) q.pop();
min_right = INF;
l = i; sz = 0;
ll cur_min = dp[i - 1]; global_min = dp[i - 1];
while(l > 1 && a[l - 1].second != a[i].second){
l --;
cur_min = min(cur_min, dp[l - 1]);
q.push(cur_min - (l - 1) * a[pre[i] + 1].first + pref[l - 1]);
}
r = i;
}
sz ++;
while(r > l && r - 1 >= pre[i] - sz + 1){
q.pop();
r --;
global_min = min(global_min, dp[r - 1]);
min_right = min(min_right, global_min - (r - 1) * a[pre[i]].first + pref[r - 1]);
}
dp[i] = pref[i] - 2 * pref[pre[i]];
dp[i] += min((pre[i] - sz) * a[pre[i]].first + min_right, (pre[i] - sz) * a[pre[i] + 1].first + q.min());
}
return dp[n];
}
