#include "wiring.h"
#include <bits/stdc++.h>
#define fst first
#define snd second
#define pb push_back
#define SZ(x) (long long)x.size()
#define ALL(x) x.begin(),x.end()
#define forn(i,a,b) for(int i = a; i<b;i++)
#define mset(a,v) memset(a,v,sizeof(a))
#ifdef D
#define debug(x) cout<<" (debug) "<<x
#else
#define debug(x) //nada
#endif
using namespace std;
typedef long long ll;
const int MAXN = 200000+5;
#define INF ((ll)10000000000000000)
ll dp[MAXN];
ll n,m;
ll mypos[MAXN];
ll mycolor[MAXN];
ll myblock[MAXN];
ll myposblock[MAXN];
vector<vector<ll>> block;
long long min_total_length(std::vector<int> r, std::vector<int> b) {
mset(dp,-1);
ll cnt = 0;
ll last = -1;
sort(ALL(r));
sort(ALL(b));
reverse(ALL(r));
reverse(ALL(b));
while(!r.empty() || !b.empty()){
if(b.empty() || (!r.empty() &&r.back()<b.back())){
if(last!=0){
block.pb({});
last=0;
}
mypos[cnt]=r.back();
mycolor[cnt]=0;
myblock[cnt]=SZ(block)-1;
myposblock[cnt]=SZ(block.back());
block.back().pb(cnt);
//block.back().pb(r.back());
r.pop_back();
cnt++;
}else{
if(last!=1){
block.pb({});
last=1;
}
mypos[cnt]=b.back();
mycolor[cnt]=0;
myblock[cnt]=SZ(block)-1;
myposblock[cnt]=SZ(block.back());
block.back().pb(cnt);
//block.back().pb(b.back());
b.pop_back();
cnt++;
}
}
forn(i,0,SZ(block)){
debug("BLOCK "<<i<<'\n');
for(auto j:block[i]) debug(" "<<j); debug('\n');
}
vector<vector<ll>> pre(SZ(block));
vector<vector<ll>> suf(SZ(block));
forn(i,0,SZ(block)){
pre[i].clear();
pre[i].resize(SZ(block[i]));
forn(j,0,SZ(block[i])){
pre[i][j]=mypos[block[i][j]]-mypos[block[i][0]];
if(j>0) pre[i][j]+=pre[i][j-1];
}
suf[i].clear();
suf[i].resize(SZ(block[i]));
for(int j = SZ(block[i])-1; j>=0; j--){
suf[i][j]=mypos[block[i].back()]-mypos[block[i][j]];
if(j+1<SZ(block[i])) suf[i][j]+=suf[i][j+1];
}
}
forn(i,0,SZ(block)){
debug("Block "<<i<<'\n');
for(auto j:pre[i]){ debug(j<<" "); } debug('\n');
for(auto j:suf[i]){ debug(j<<" "); } debug('\n');
debug('\n');
}
for(int i = 0; i<cnt; i++){
dp[i]=INF;
}
vector<ll> preff;
vector<ll> suff;
for(int i = 0; i<cnt; i++){
if(myblock[i]-1>=0){
/*
forn(j,0,SZ(block[myblock[i]-1])){
ll ib = myblock[i];
ll ni = block[ myblock[i]-1 ][j];
ll cost = mypos[ block[ ib ][0] ] - mypos[ block[ ib-1 ].back() ];
ll maxi = max(SZ(block[ib-1])-(j+1) , myposblock[i]+1);
dp[i]=min(dp[i],dp[ni] + pre[ib][myposblock[i]] + suf[ib-1][j+1] + cost * maxi);
}*/
ll ruse = myposblock[i]+1;
ll ib = myblock[i];
ll cost = mypos[ block[ ib ][0] ] - mypos[ block[ ib-1 ].back() ];
/*cout<<SZ(block[ib-1])-ruse<< " ind suff\n";
cout<<suff[ max((ll)0, SZ(block[ib-1]) - ruse ) ] + cost * ruse + pre[ib][ruse-1]<<'\n';
cout<<(ruse>=SZ(preff)?INF:preff[ SZ(block[ib-1]) - ruse ]) + pre[ib][ruse-1]<<'\n';*/
dp[i]=min(dp[i], suff[ max((ll)0, SZ(block[ib-1]) - (ruse+1) ) ] + cost * ruse + pre[ib][ruse-1] );
dp[i]=min(dp[i], (ruse>=SZ(preff)?INF:preff[ SZ(block[ib-1]) - (ruse+1) ]) + pre[ib][ruse-1] );
if(myblock[i]-2 == -1){
ll ib = myblock[i];
ll cost = mypos[ block[ ib ][0] ] - mypos[ block[ ib-1 ].back() ];
ll maxi = max(SZ(block[ib-1]) , myposblock[i]+1);
dp[i]=min(dp[i], pre[ib][myposblock[i]] + suf[ib-1][0] + cost * maxi);
//cout<<i<<" cae aca\n";
}else if(myblock[i]-2>=0){
ll ib = myblock[i];
ll cost = mypos[ block[ ib ][0] ] - mypos[ block[ ib-1 ].back() ];
ll maxi = max(SZ(block[ib-1]) , myposblock[i]+1);
ll ni = block[myblock[i]-2].back();
dp[i]=min(dp[i],dp[ni] + pre[ib][myposblock[i]] + suf[ib-1][0] + cost * maxi);
}
}
if(myposblock[i]==SZ(block[myblock[i]])-1 && myblock[i]+1<SZ(block)){
preff.clear();
suff.clear();
ll ib = myblock[i];
ll cost = mypos[ block[ ib+1 ][0] ] - mypos[ block[ ib ].back() ];
forn(j,0,SZ(block[myblock[i]])){
preff.pb(dp[block[ib][j]]+cost*(SZ(block[ib])-(j+1))+(j+1<SZ(suf[ib])?suf[ib][j+1]:0));
if(j>0) preff.back()=min(preff.back(), preff[j-1]);
}
forn(j,0,SZ(suf[ib])){
suff.pb(dp[block[ib][j]]+(j+1<SZ(suf[ib])?suf[ib][j+1]:0));
}
for(int j = SZ(block[ib])-1; j>=0; j--){
if(j+1<SZ(block[ib])) suff[j]=min(suff[j],suff[j]);
}
debug("new \n");
debug("preff ");for(auto j:preff) debug(j<<" "); debug("\n");
debug("suff ");for(auto j:suff) debug(j<<" "); debug("\n");
}
debug("dp "<<i<<" "<<dp[i]<<'\n');
}
return dp[cnt-1];
}
