#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
const ll inf = 1e18;
int n, m;
ll r[maxn], b[maxn], x[maxn], t[maxn];
int sz, cp_sz[maxn];
vector < ll > st[maxn], pref[maxn];
vector < ll > dp[maxn];
ll get_range(int row, int l, int r)
{
if (r < l)
return 0;
if (l == 0)
return pref[row][r];
return pref[row][r] - pref[row][l - 1];
}
ll min_total_length(vector<int> R, vector<int> B)
{
n = R.size();
m = B.size();
vector < pair < int, int > > vec;
for (int i = 1; i <= n; i ++)
r[i] = R[i - 1], vec.push_back({r[i], 0});
for (int i = 1; i <= m; i ++)
b[i] = B[i - 1], vec.push_back({b[i], 1});
sort(vec.begin(), vec.end());
for (int i = 1; i <= n + m; i ++)
{
x[i] = vec[i - 1].first;
t[i] = vec[i - 1].second;
}
st[1].push_back(x[1]);
cp_sz[1] ++;
sz = 1;
for (int i = 2; i <= n + m; i ++)
{
if (t[i] != t[i - 1])
sz ++;
cp_sz[sz] ++;
st[sz].push_back(x[i]);
}
for (int i = 1; i <= sz; i++)
{
dp[i].resize(cp_sz[i] + 1, inf);
pref[i].resize(cp_sz[i]);
pref[i][0] = st[i][0];
for (int j = 1; j < cp_sz[i]; j ++)
pref[i][j] = pref[i][j - 1] + st[i][j];
}
dp[1][cp_sz[1]] = 0;
for (int i = 2; i <= sz; i ++)
{
for (int tk = cp_sz[i - 1]; tk > 0; tk --)
{
dp[i - 1][tk - 1] = min(dp[i - 1][tk - 1], dp[i - 1][tk] + (st[i][0] - st[i - 1][cp_sz[i - 1] - tk]));
}
for (int tk = 0; tk <= min(cp_sz[i - 1], cp_sz[i]); tk ++)
{
dp[i][cp_sz[i] - tk] = min(dp[i][cp_sz[i] - tk], dp[i - 1][tk] +
get_range(i, 0, tk - 1) - get_range(i - 1, cp_sz[i - 1] - tk, cp_sz[i - 1] - 1));
}
for (int tk = cp_sz[i]; tk > 0; tk --)
{
dp[i][tk - 1] = min(dp[i][tk - 1], dp[i][tk] + (st[i][cp_sz[i] - tk] - st[i - 1].back()));
}
}
return dp[sz][0];
}
