#include "wiring.h"
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define rep(i, n) for(int i = 1; i <= (n); ++i)
#define REP(i, n) for(int i = 0; i < (n); ++i)
#define forn(i, l, r) for(int i = (l); (i) <= (r); ++i)
#define ford(i, r, l) for(int i = (r); (i) >= (l); --i)
#define endl "\n"
#define fi first
#define se second
#define pb push_back
#define pll pair<ll, ll>
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a.size())
#define task "note"
template<typename T> bool maximize(T &res, const T &val) {if(res < val) {res = val; return 1;} return 0;}
template<typename T> bool minimize(T &res, const T &val) {if(res < val) return 0; res = val; return 1;}
inline int readInt() {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();int n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline ll readLong() {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();ll n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline string readString() {char c;while(c=getchar(),c==' '||c=='\n'||c=='\t');string s({c});while(c=getchar(),c!=EOF&&c!=' '&&c!='\n'&&c!='\t')s+=c;return s;}
const int N = 5000 + 3;
const int LOG = 12;
const int INF = 2e9;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
double get_cur_time() {return chrono::steady_clock::now().time_since_epoch().count();}
ll min_total_length(vector<int> r, vector<int> b)
{
vector<pii> a;
for(int x : r) a.pb({x, 0});
for(int x : b) a.pb({x, 1});
vector<int> dist(sz(a) + 1, INF);
sort(all(a));
for(int i = 1, lst = -1; i <= sz(a); ++i)
{
if(i > 1 && a[i - 1].se != a[i - 2].se) lst = i - 1;
if(lst != -1) minimize(dist[i], abs(a[i - 1].fi - a[lst - 1].fi));
}
for(int i = sz(a), lst = -1; i >= 1; --i)
{
if(i < sz(a) && a[i - 1].se != a[i].se) lst = i + 1;
if(lst != -1) minimize(dist[i], abs(a[i - 1].fi - a[lst - 1].fi));
}
vector<ll> pre(sz(a) + 1, 0);
vector<ll> dp(sz(a) + 1, 0);
for(int i = 1; i <= sz(a); ++i) pre[i] = pre[i - 1] + a[i - 1].fi;
function<ll(int, int)> get_sum = [&](int l, int r) {
return pre[r] - pre[l - 1];
};
// for(int i = 1; i <= sz(a); ++i)
// {
// cout << a[i - 1].fi << " " << a[i - 1].se << " " << dist[i] << endl;
// }
for(int i = 1, lst = 1; i <= sz(a); ++i)
{
int j = i;
while(j <= sz(a) && a[j - 1].se == a[i - 1].se) ++j;
--j;
for(int k = i; k <= j; ++k)
{
dp[k] = dp[k - 1] + dist[k];
int x = 2 * i - k - 1;
if(x >= lst) minimize(dp[k], dp[x - 1] + get_sum(i, k) - get_sum(x, i - 1));
}
lst = i;
i = j;
}
return dp[sz(a)];
}
