#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) ;
vector<long long> meuValor(n+m) ;
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[i] = s[ fim[i] ] - s[ ini[i] ] - (ll)( fim[i] - ini[i] ) * loc[ ini[i] ].ff + dp[i+1];
bestIndex[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( last != fim[ fim[i]+1 ] )
{
possible2 = s[last] - s[ fim[i] ] - (ll)(last-fim[i]) * loc[ fim[i]+1 ].ff ;
int shortcut = bestIndex[ last+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( 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] );
lp(j,ini[i],fim[i]+1)
meuValor[j] = s[j] - s[ i-1 ] - (ll)( j - i + 1 ) * loc[i].ff + dp[j+1] ;
bestIndex[ fim[i] ] = i ;
for(int j = fim[i] - 1 ; j >= i ; j-- )
{
bestIndex[j] = bestIndex[j+1] ;
if( meuValor[j] < meuValor[ bestIndex[j] ] ) bestIndex[j] = j ;
}
}
}
return dp[0] ;
}
