#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<ll>
#define vvi vector<vi>
#define pii pair<ll,ll>
#define vii vector<pii>
#define fi first
#define se second
#define pb push_back
const ll INF=1000000000000000001;
void debug(vi v){
for (ll x:v) cerr << x << ' ';
cerr << '\n';
}
long long min_total_length(std::vector<int> r, std::vector<int> b) {
int n=r.size()+b.size();
vii v;
for (int x: r) v.pb(pii{x,0});
for (int x: b) v.pb(pii{x,1});
sort(v.begin(),v.end());
vvi blocks;
blocks.pb(vi{v[0].fi});
for (int i=1;i<n;i++){
if (v[i].se==v[i-1].se) blocks[blocks.size()-1].pb(v[i].fi);
else blocks.pb(vi{v[i].fi});
}
int m=blocks.size();
vvi dp(m);
for (int i=0;i<m;i++) dp[i]=vi(blocks[i].size()+1,INF);
vvi distmax=blocks;
vvi distmin=blocks;
for (int i=0;i<m;i++){
int k=blocks[i].size();
distmax[i][k-1]=0;
for (int j=k-2;j>=0;j--)
distmax[i][j]=distmax[i][j+1]+blocks[i][k-1]-blocks[i][j];
distmin[i][0]=0;
for (int j=1;j<k;j++)
distmin[i][j]=distmin[i][j-1]+blocks[i][j]-blocks[i][0];
distmax[i].pb(0);
distmin[i].pb(0);
}
/*
cerr << "Blocks: " << '\n';
for (vi w:blocks){
for (int x:w) cerr << x << ' ';
cerr << '\n';
}
*/
dp[0][0]=0;
vvi minimpeque(m);
vvi minimgrande(m);
{
int i=0;
int k=blocks[i].size();
vi peque(k+1);
vi grande(k+1,-1);
for (int j=0;j<=k;j++){
peque[j]=dp[i][j]+distmax[i][j]; //cuando cojes j
if (i+1<m)
grande[j]=dp[i][j]+distmax[i][j]+(k-j)*(blocks[i+1][0]-blocks[i][k-1]);
}
minimpeque[i]=peque;
for (int j=k-1;j>=0;j--) minimpeque[i][j]=min(minimpeque[i][j+1],peque[j]);
minimgrande[i]=grande;
for (int j=1;j<=k;j++) minimgrande[i][j]=min(minimgrande[i][j-1],grande[j]);
}
for (int i=1;i<m;i++){
int k=blocks[i].size();
int prek=blocks[i-1].size();
dp[i][0]=dp[i-1][prek];
for (int j=0;j<k;j++){ //pillamos los j de la izquierda
// a>b
dp[i][j+1]=minimpeque[i-1][max((int) 0,prek-j-1)]
+distmin[i][j]+(j+1)*(blocks[i][0]-blocks[i-1][prek-1]);
// a<b
//cerr << "mira: " << dp[i][j+1] << ' ';
if (prek-j-1>=0){
dp[i][j+1]=min(dp[i][j+1]
,minimgrande[i-1][prek-j-1]+distmin[i][j]);
}
//cerr << dp[i][j+1] << '\n';
}
vi peque(k+1);
vi grande(k+1,-1);
for (int j=0;j<=k;j++){
peque[j]=dp[i][j]+distmax[i][j]; //cuando cojes j
if (i+1<m)
grande[j]=dp[i][j]+distmax[i][j]+(k-j)*(blocks[i+1][0]-blocks[i][k-1]);
}
minimpeque[i]=peque;
for (int j=k-1;j>=0;j--) minimpeque[i][j]=min(minimpeque[i][j+1],peque[j]);
minimgrande[i]=grande;
for (int j=1;j<=k;j++) minimgrande[i][j]=min(minimgrande[i][j-1],grande[j]);
}
/*
cerr << "DP:\n";
for (int i=0;i<m;i++) debug(dp[i]);
cerr << "Mingrande:\n";
for (int i=0;i<m;i++) debug(minimgrande[i]);
*/
return dp[m-1][dp[m-1].size()-1];
}
