#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 calc(int l1, int r1, int l2, int r2, vector<pair<int, int>> &a, vector<ll> &pref){
ll ans = pref[r2] - pref[l2 - 1] - (pref[r1] - pref[l1 - 1]);
if(r2 - l2 > r1 - l1){
ans -= (ll) (r2 - l2 - (r1 - l1)) * a[r1].first;
} else ans += (ll) (r1 - l1 - (r2 - l2)) * a[l2].first;
return ans;
}
ll get_min(vector<ll> &dp, int i, int j){
ll ans = INF;
for(int k=i; k<=j; k++) ans = min(ans, dp[k]);
return ans;
}
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 = INF; global_min = INF;
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());
for(int j=l; j<=pre[i]; j++) dp[i] = min(dp[i], get_min(dp, j - 1, i) + calc(j, pre[i], pre[i] + 1, i, a, pref));
}
return dp[n];
}
