#include "wiring.h"
#include <bits/stdc++.h>
#define FOR(i,p,k) for(int i=(p);i<=(k);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) (int((x).size()))
#define all(x) (x).begin(),(x).end()
#define inf 1000000000000000000ll
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll, bool> plb;
vector<ll> pom(vector<ll> popdp, vector<ll> poppoz, vector<ll> terpoz){
//~ printf("poppoz: ");
//~ for(ll x : poppoz) printf("%lld ", x);
//~ printf("\n");
//~ printf("popdp: ");
//~ for(ll x : popdp) printf("%lld ", x);
//~ printf("\n");
//~ printf("terpoz: ");
//~ for(ll x : terpoz) printf("%lld ", x);
//~ printf("\n");
int n = ssize(poppoz);
int m = ssize(terpoz);
ll dodaj = 0ll;
for(int i = n-1; ~--i;){
dodaj += poppoz[n-1]-poppoz[i];
popdp[i] += dodaj;
}
ll delta = terpoz[0]-poppoz[n-1];
vector<ll> dp(m+1);
dp[0] = popdp[n];
FOR(i, 1, m){
dp[i] = inf;
REP(j, n) dp[i] = min(dp[i], popdp[j] + delta*max(i, n-j));
}
dodaj = 0ll;
FOR(i, 2, m){
dodaj += terpoz[i-1]-terpoz[0];
dp[i] += dodaj;
}
//~ printf("dp: ");
//~ for(ll x : dp) printf("%lld ", x);
//~ printf("\n");
//~ printf("\n");
return dp;
}
ll min_total_length(vector<int> r, vector<int> b){
vector<plb> vec;
for(int x : r) vec.emplace_back(x, 0);
for(int x : b) vec.emplace_back(x, 1);
sort(all(vec));
vector<ll> dp, poppoz, terpoz;
REP(i, ssize(vec)){
terpoz.emplace_back(vec[i].fi);
if(i+1 == ssize(vec) || vec[i+1].se != vec[i].se){
if(dp.empty()) dp.resize(ssize(terpoz)+1, inf), dp[0] = 0ll;
else dp = pom(dp, poppoz, terpoz);
poppoz = terpoz, terpoz.clear();
}
}
return dp.back();
}
