#include "wiring.h"
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
using ll = long long;
ll min_total_length(vector<int> r, vector<int> b)
{
/*vector<vector<ll>> dp(r.size(), vector<ll>(b.size()));
for (int i = 0; i < b.size(); ++i)
{
dp[0][i] = abs(r[0] - b[i]);
if (i != 0) dp[0][i] += dp[0][i - 1];
}
for (int i = 1; i < r.size(); ++i)
{
for (int j = 0; j < b.size(); ++j)
{
dp[i][j] = dp[i - 1][j] + abs(r[i] - b[j]);
if (j != 0)
{
dp[i][j] = min({dp[i][j], dp[i][j - 1] + abs(r[i] - b[j]),
dp[i - 1][j - 1] + abs(r[i] - b[j])});
}
}
}
return dp.back().back();*/
vector<pair<ll, bool>> points;
for (int i : r) points.emplace_back(i, 0);
for (int i : b) points.emplace_back(i, 1);
sort(points.begin(), points.end());
int n = points.size();
vector<ll> dp(n, 1e18);
for (int i = 1; i < n; ++i)
{
int last;
ll sum = 0, cnt = 1;
for (last = i - 1; last >= 0 && points[last].second == points[i].second; --last)
{
sum += (points[last + 1].first - points[last].first) * (i - last);
++cnt;
}
if (last < 0) continue;
dp[i] = dp[last] + sum + cnt * (points[last + 1].first - points[last].first);
int st = last;
ll sum2 = 0;
for (; last >= 0 && points[last].second != points[i].second; --last)
{
sum2 += points[st].first - points[last].first;
ll res = sum2 + sum + max(cnt, st - last + 1ll) * (points[st + 1].first - points[st].first);
if (last > 0) res += dp[last - 1];
dp[i] = min(dp[i], res);
}
}
return dp.back();
}
