#include "wiring.h"
#include <bits/stdc++.h>
#define debug printf
#define lp(i,a,b) for(int i = a ; i < b; i++)
#define pb push_back
#define ff first
#define ss second
#define mk make_pair
#define pii pair<int,int>
#define ll long long
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size())
const ll inf = 1e15+10 ;
using namespace std ;
long long min_total_length(vector<int> r, vector<int> b)
{
int n = sz(r) ;
int m = sz(b) ;
vector< pair<long long,int> > loc(n+m) ;
for(int i = 0 ; i < n ; i++ ) loc[i] = make_pair( r[i] , 0 ) ;
for(int i = n ; i < n+m ; i++ ) loc[i] = make_pair(b[i-n] , 1 ) ;
sort(all(loc)) ;
vector<int> ini(n+m,-1) , fim(n+m,-1) , bestIndex(n+m,-1) ;
vector< long long > dp(n+m+1, inf ) , minPrefix(n+m, inf) , s(n+m,0) ;
for(int i = 0 ; i < sz(loc) ; i++ )
{
if(ini[i] == -1) ini[i] = i ;
if( i < sz(loc)-1 && loc[i+1].ss == loc[i].ss ) ini[i+1] = ini[i] ;
else
{
for(int j = ini[i] ; j <= i ; j++ ) fim[j] = i ;
}
s[i] = loc[i].ff ;
if(i) s[i] += s[i-1] ;
}
dp[n+m] = 0LL ;
for(int i = n+m-1 ; i >= 0 ; i-- )
{
if( fim[i] == n+m-1 )
{
//I'm in the last group
//There is really not much I can do
minPrefix[ fim[i] ] = s[ fim[i] ] - s[ ini[i] ] - (ll)( fim[i] - ini[i] ) * loc[ ini[i] ].ff ;
bestIndex[ ini[i] ] = fim[i] ;
continue ;
}
//I'm not in the last group
//I can calculate proper things now
//Constant part
dp[i] = loc[ fim[i] + 1 ].ff * (fim[i] - i + 1) - ( s[ fim[i] ] - ( (i == 0) ? 0 : s[i-1] ) ) ;
//Now I gotta check some min's
int last = min(fim[i]+1 + fim[i] - i , fim[ fim[i]+1 ] ) ;
ll possible1 = minPrefix[ last ] ;
ll possible2 = inf ;
if( bestIndex[fim[i]+1] > last )
{
possible2 = s[last] - s[ fim[i] ] - (ll)(last-fim[i]) * loc[ fim[i]+1 ].ff ;
int shortcut = bestIndex[ fim[i]+1 ] ;
possible2 += dp[ shortcut+1 ] + s[ shortcut ] - s[ last ] - (ll)( shortcut - last ) * loc[ fim[i] ].ff ;
}
dp[i] += min( possible1, possible2 ) ;
if(!ini[i]) continue ;
if( bestIndex[ini[i]] == -1 ) bestIndex[ini[i]] = i ;
else
{
int &shortcut = bestIndex[ini[i]] ;
ll valBest = dp[ shortcut+1 ] + s[ shortcut ] - s[ ini[i]-1 ] - (ll)( shortcut - ini[i]+1 ) * loc[ ini[i]-1 ].ff ;
ll valNow = dp[i+1] + s[i] - s[ ini[i]-1 ] * (ll)( i - ini[i] +1 ) * loc[ ini[i]-1 ].ff ;
if( valNow < valBest ) shortcut = i ;
}
if( i == ini[i] )
{
minPrefix[i] = dp[i+1] ;
for(int j = i+1 ; j <= fim[i] ; j++ )
minPrefix[j] = min(minPrefix[j-1], s[j] - s[i] - (ll)(j-i) * loc[i].ff + dp[j+1] );
}
}
return dp[0] ;
}
