#include <bits/stdc++.h>
#include "wiring.h"
#define pii pair<long long, long long>
#define x first
#define y second
using namespace std;
const int N = 2e5 + 10;
vector<pii> vec;
long long seg[2][N<<2], dp[N], n, sumr[N], suml[N], lenl[N], lenr[N], pre[N], pos[N];
vector<long long> plug[2];
void update( int t, int pos, long long val, int l = 1, int r = n, int idx = 1 ) {
//printf("l r%d %d \n",l,r);
if( l == r ) return void( seg[t][idx] = val );
int mid = l + r >> 1;
if( pos <= mid ) update( t, pos, val, l, mid, idx<<1 );
else update( t, pos, val, mid + 1, r, idx<<1|1);
seg[t][idx] = min( seg[t][idx<<1], seg[t][idx<<1|1] );
}
long long query( int t, int ll, int rr, int l = 1, int r = n, int idx = 1 ) {
if( ll > rr ) return 1e18;
if( l > rr || r < ll ) return 1e18;
if( l >= ll && r <= rr ) return seg[t][idx];
int mid = l + r >> 1;
return min( query( t, ll, rr, l, mid, idx<<1 ), query( t, ll, rr, mid + 1, r, idx<<1|1 ) );
}
long long min_total_length( vector<int> R, vector<int> B ) {
fill( seg[0], seg[0] + 4*N, 1e18 );
fill( dp, dp + N, 1e18 );
n = R.size() + B.size();
for( int i = 0 ; i < R.size() ; i++ ) plug[0].emplace_back( ( long long )R[i] );
for( int i = 0 ; i < B.size() ; i++ ) plug[1].emplace_back( ( long long )B[i] );
vec.emplace_back( -1e12, -1e12 ), vec.emplace_back( 1e12, 1e12 );
for( int i : R ) vec.emplace_back( i, 0 );
for( int i : B ) vec.emplace_back( i, 1 );
//printf("hello");
sort( vec.begin(), vec.end() );
for( int i = 1 ; i <= n ; i++ ) {
if( vec[i].y == vec[i-1].y ) {
lenl[i] = lenl[i-1] + 1;
pre[i] = pre[i-1];
suml[i] = suml[i-1] + vec[i].x;
}
else {
lenl[i] = 1;
pre[i] = i;
suml[i] = vec[i].x;
}
}
//printf("hello");
for( int i = n ; i >= 1 ; i-- ) {
if( vec[i].y == vec[i+1].y ) {
lenr[i] = lenr[i+1] + 1;
pos[i] = pos[i+1];
sumr[i] = sumr[i+1] + vec[i].x;
}
else {
lenr[i] = 1;
pos[i] = i;
sumr[i] = vec[i].x;
}
}
//printf("hello");
dp[0] = 0;
for( int i = 1 ; i <= n ; i++ ) {
//printf("%lld\n",query( 0, 1, 1 ) );
//printf("pre[%d] : %lld\n",i,pre[i]);
int c = vec[i].y, o = vec[i].y^1;
int idx = lower_bound( plug[o].begin(), plug[o].end(), vec[i].x ) - plug[o].begin();
// printf("idx:%d\n",idx);
if( idx != plug[o].size() ) dp[i] = min( dp[i], dp[i-1] + plug[o][idx] - vec[i].x );
if( idx ) dp[i] = min( dp[i], dp[i-1] + vec[i].x - plug[o][idx-1] );
//printf("dp: %lld\n",dp[i]);
if( pre[i] != 1 ) {
int l = pre[pre[i]-1];
long long mx = vec[pre[i]-1].x;
//printf("debug %lld %lld ",pre[i],vec[pre[i]-1].x);
//printf("debug%lld %lld %d %lld\n",max( ( long long )l, pre[i]-lenl[i] ),pre[i]-1, l, pre[i]-lenl[i]-1);
long long qq = query( 0, max( ( long long )l, pre[i] - lenl[i] ), pre[i]-1 );
//printf("%lld\n",qq);
dp[i] = min( dp[i], qq + suml[i] - 1ll * lenl[i] * mx );
long long qq2 = query( 1, l, pre[i] - lenl[i] - 1 );
//printf("%lld\n",qq2);
dp[i] = min( dp[i], qq2 + suml[i] - vec[pre[i]].x*lenl[i] );
}
//printf("%lld %lld %lld %lld\n",sumr[i],lenr[i],vec[pos[i]].x,vec[pos[i]+1].x);
//printf("%d : dp: %lld up0 %lld up1 %lld\n",i,dp[i],dp[i-1] - sumr[i] + lenr[i] * vec[pos[i]].x,dp[i-1] - sumr[i] + vec[pos[i]+1].x*lenr[i]);
update( 0, i, dp[i-1] - sumr[i] + lenr[i] * vec[pos[i]].x );
update( 1, i, dp[i-1] - sumr[i] + vec[pos[i]+1].x*lenr[i] );
}
return dp[n];
}
/*int main() {
int n, m;
vector<int> v, v2;
scanf("%d %d",&n,&m);
for( int i = 0, a ; i < n ; i++ ) {
scanf("%d",&a);
v.emplace_back( a );
}
for( int i = 0,a ; i < m ; i++ ) {
scanf("%d",&a);
v2.emplace_back( a );
}
printf("%lld",min_total_length( v, v2 ) );
}*/
