#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
ll solve2(vector<int> r, vector<int> b){
int n = int(r.size()), m = int(b.size());
ll ans = 0;
for(int i = 0; i < m; i++) ans += b[i];
for(int i = 0; i < n; i++) ans -= r[i];
if(n < m) for(int i = 0; i < m-n; i++) ans -= r.back();
if(m < n) for(int i = 0; i < n-m; i++) ans += b.front();
return ans;
}
ll min_total_length(vector<int> r, vector<int> b) {
int n = int(r.size()), m = int(b.size());
vector<pair<int, int>> a;
for(int i : r) a.emplace_back(i, 0);
for(int i : b) a.emplace_back(i, 1);
sort(a.begin(), a.end());
vector<ll> dp(n+m+1);
for(int i = 1; i <= n+m; i++){
dp[i] = INF;
vector<int> diff;
int cnt = 0;
for(int j = i-1; j >= 0; j--){
if(diff.empty() || diff.back() != a[j].second){
if((int)diff.size() == 2 && cnt > 1) break;
if((int)diff.size() > 2) break;
diff.push_back(a[j].second);
cnt = 1;
}
else cnt++;
if((int)diff.size() == 2){
vector<int> x, y;
for(int k = j; k < i; k++) if(a[k].second == 0) x.push_back(a[k].first); else y.push_back(a[k].first);
ll ans = solve2(x, y);
dp[i] = min(dp[i], dp[j]+abs(ans));
}
else if((int)diff.size() == 3){
int mid = diff[1];
bool vis = false;
ll ans = 0;
for(int k = j; k < i; k++){
if(a[k].second == mid){
vis = true;
ans += ll(k-j - (i-1-k))*a[k].first;
}
else{
if(!vis) ans -= a[k].first;
else ans += a[k].first;
}
}
dp[i] = min(dp[i], dp[j]+ans);
}
}
}
return dp[n+m];
}
