#include "wiring.h"
#include <iostream>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <fstream>
#include <cmath>
#include <vector>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <stack>
#include <queue>
#include <assert.h>
#include <limits>
#include <cstdio>
#include <complex>
using namespace std;
typedef long long ll;
vector<ll> seqinds;
vector<ll> prefl;
vector<ll> prefr;
vector<ll> dl;
vector<ll> dr;
vector<ll> len;
ll n;
ll ns;
ll INF = 1e18;
void processData(vector<int> &r, vector<int> &b){
vector<pair<ll, bool>> seq;
for (ll i : r) {
seq.push_back({i, false});
}
for (ll i : b) {
seq.push_back({i, true});
}
n = seq.size();
sort(seq.begin(), seq.end());
ll mx = seq.back().first;
for (auto p : seq) {
dl.push_back(p.first);
dr.push_back(mx-p.first);
}
prefl.resize(n+1);
prefr.resize(n+1);
for (ll i = 0; i<n; i++){
prefl[i+1] = prefl[i]+dl[i];
}
for (ll i = n-1; i>=0; i--){
prefr[i] = prefr[i+1]+dr[i];
}
bool curval = seq[0].second;
ll curind = 0;
seqinds.push_back(curind);
for (ll i = 0; i<n; i++) {
if (seq[i].second != curval) {
curind = i;
seqinds.push_back(curind);
curval = seq[i].second;
}
}
ns = seqinds.size();
seqinds.push_back(n);
for (ll i = 0; i<seqinds.size()-1; i++) {
len.push_back(seqinds[i+1]-seqinds[i]);
}
}
//void processData2(vector<int> &r, vector<int> &b) {
// vector<pair<ll, bool>> seq;
// for (ll i : r) {
// seq.push_back({i, false});
// }
// for (ll i : b) {
// seq.push_back({i, true});
// }
// n = seq.size();
// sort(seq.begin(), seq.end());
// ll mx = seq.back().first;
// for (auto p : seq) {
// dl.push_back(p.first);
// dr.push_back(mx-p.first);
// }
// prefl.resize(n+1);
// prefr.resize(n+1);
// for (ll i = 0; i<n; i++) {
// prefl[i+1] = prefl[i]+dl[i];
// }
// for (ll i = n-1; )
//}
void display(string s, vector<ll> &v){
cout << s << ": ";
for (ll i : v) {
cout << i << ' ';
} cout << '\n';
}
ll lsum(ll i, ll l) {
ll xi = seqinds[i];
return prefl[xi+l]-prefl[xi]-l*dl[xi];
}
ll rsum(ll i, ll r) {
ll xi1 = seqinds[i+1];
return prefr[xi1-r]-prefr[xi1]-r*dr[xi1];
}
ll performDP() {
ll mxlen = 0;
for (ll i : len) {
mxlen = max(mxlen, i);
}
vector<vector<ll>> dp(2, vector<ll>(mxlen+1, INF));
vector<vector<ll>> dpgeq(2, vector<ll>(mxlen+1, INF));
bool cur = false;
dp[!cur][0] = 0;
dpgeq[!cur][0] = 0;
for (ll i = 0; i<ns; i++) {
//cout<<"dp "<<i<<endl;
ll xi1 = seqinds[i+1];
ll ci = dr[xi1-1]-dr[xi1];
ll minpref = INF;
ll maxprev = max(len[i], ((i==0) ? 0 : len[i-1]));
//ll maxprev = mxlen;
for (ll r = 0; r<=maxprev; r++) {
ll newl = len[i]-r;
if (newl<0) {
newl = 0;
}
ll newmin = dp[!cur][newl]+lsum(i, newl)+rsum(i, len[i]-newl)+ci*newl;
//cout<<"at r = "<<r<<": new value is "<<newmin<<'\n';
minpref = min(minpref,newmin);
dp[cur][r] = minpref+ci*(r-len[i]);
}
if (i==ns-1) {
break;
}
for (ll r = maxprev+1; r<=len[i+1]; r++) {
dp[cur][r] = dp[cur][r-1]+ci;
}
/*for (ll x = 0; x<=max(maxprev,len[i+1]); x++){
cout<<dp[cur][x]<<' ';
}cout<<'\n';*/
for (ll r = max(maxprev, len[i+1])-1; r>=0; r--) {
dp[cur][r] = min(dp[cur][r], dp[cur][r+1]);
}
/*for (ll x = 0; x<=max(maxprev,len[i+1]); x++){
cout<<dp[cur][x]<<' ';
}cout<<'\n';*/
cur=!cur;
}
/*for (int i = 0; i<ns; i++){
for (int r = 0; r<mxlen; r++){
//dp(i,r)
for (int l = max(len[i]-r,0); l<=len[i]; l++){
dp[cur][r]=min(dp[cur][r])
}
}
}*/
return dp[cur][0];
}
ll min_total_length(std::vector<int> r, std::vector<int> b) {
processData(r,b);
/*display("seqinds",seqinds);
display("prefl",prefl);
display("prefr",prefr);
display("len",len);
display("distance l",dl);
display("distance r",dr);*/
/*while (true){
char c;
ll a,b;
cin>>c>>a>>b;
if (c=='l'){
cout<<lsum(a,b)<<endl;
} else if (c=='r'){
cout<<rsum(a,b)<<endl;
} else {
assert(1==0);
}
}*/
return performDP();
}
