#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
const int maxn = 2e5+10;
int n, m, pf[maxn], pfmn[maxn], sfmn[maxn], val[maxn];
int min_total_length(std::vector<int32_t> r, std::vector<int32_t> b) {
n = r.size();
m = b.size();
vector<pair<int,int>> cn;
for(auto x : r) cn.pb(mp(x,0));
for(auto x : b) cn.pb(mp(x,1));
n+= m;
sort(all(cn));
for(int i = 0; i < n; i++) {
if(i != 0) pf[i]+= pf[i-1];
pf[i]+= cn[i].fr;
}
int L = n,R = n;
vector<int> dp(n+1);
dp[n] = 0;
int k;
for(int i = n-1; i >= 0; i--) {
if(i != n-1 && cn[i].sc != cn[i+1].sc) {
R = L-1;
L = i+1;
k = i;
for(int j = L; j <= R; j++) {
val[j] = pf[j]-pf[k] - (j-k)*cn[k+1].fr;
}
//prefix that we have more R than B
for(int j = L; j <= R; j++) {
if(j == L) pfmn[j] = inf;
else pfmn[j] = pfmn[j-1];
pfmn[j] = min(pfmn[j],val[j]+min(dp[j+1],dp[j]));
}
for(int j = R; j >= L; j--) {
if(j == R) sfmn[j] = inf;
else sfmn[j] = sfmn[j+1];
sfmn[j] = min(sfmn[j],val[j]+min(dp[j+1],dp[j]) + (cn[k+1].fr-cn[k].fr)*(j-k));
}
}
if(L == n) {
dp[i] = inf;
continue;
}
int p = 2*k-i+1;
p = min(p,R);
//vejo os j <= p
int cons = (k-i+1)*cn[k].fr -pf[k] + (i != 0 ? pf[i-1] : 0);
dp[i] = pfmn[p]+cons+(k-i+1)*(cn[k+1].fr-cn[k].fr);
if(p != R) dp[i] = min(dp[i],sfmn[p+1]+cons);
// cout << i << " = " << dp[i] << endl;
}
return dp[0];
}
// int32_t main() {
// ios::sync_with_stdio(false); cin.tie(0);
// freopen("in.in", "r", stdin);
// int32_t N, M;
// assert(2 == scanf("%d %d", &N, &M));
// vector<int32_t> r(N), b(M);
// for(int i = 0; i < N; i++)
// assert(1 == scanf("%d", &r[i]));
// for(int i = 0; i < M; i++)
// assert(1 == scanf("%d", &b[i]));
// long long res = min_total_length(r, b);
// printf("%lld\n", res);
// return 0;
// }
