#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 205;
ll dp[N][N][4];
const ll M = 1000000000000000000LL;
long long min_total_length(std::vector<int> r, std::vector<int> b) {
int n = r.size();
int m = b.size();
if (r[n - 1] <= b[0])
{
int cur = n - 1;
ll res = 0;
for (int i = 0; i < m; i++)
{
if (cur >= 0) res += b[i] - r[cur];
else res += b[i] - r[n - 1];
cur--;
}
while (cur >= 0)
{
res += b[0] - r[cur];
cur--;
}
return res;
}
if (false && n <= 200 && m <= 200)
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
for (int k = 0; k < 4; k++) dp[i][j][k] = M;
}
}
dp[0][0][0] = 0;
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= m; j++)
{
for (int k = 0; k < 4; k++)
{
if (i < n)
{
if (i == 0 || k & 1)
{
dp[i + 1][j][k & 2] = min(dp[i][j][k], dp[i + 1][j][k & 2]);
if (j != 0) dp[i + 1][j][3] = min(dp[i][j][k] + abs(r[i] - b[j - 1]), dp[i + 1][j][3]);
//cout << i << " " <<j << " " << dp[i + 1][j][3] << endl;
}
}
if (j < m)
{
if (j == 0 || k & 2)
{
dp[i][j + 1][k & 1] = min(dp[i][j][k], dp[i][j + 1][k & 1]);
if (i != 0) dp[i][j + 1][3] = min(dp[i][j][k] + abs(r[i - 1] - b[j]), dp[i][j + 1][3]);
}
}
//cout << i << " " << j << " " << k << " "<< dp[i][j][k] << endl;
}
}
}
return dp[n][m][3];
}
vector<array<int, 2>> byType;
for (int i = 0; i <n; i++)
{
byType.push_back({r[i], 0});
}
for (int i = 0; i < m; i++)
{
byType.push_back({b[i], 1});
}
sort(byType.begin(), byType.end());
vector<ll> best(n + m, M);
for (int i = 1; i < n + m; i++)
{
if (byType[i][1] != byType[i - 1][1])
{
int r = i;
while (r + 1 < n + m && byType[r + 1][1] == byType[r][1]) r++;
int m = i;
int l = m - 1;
while (l - 1 >= 0 && byType[l - 1][1] == byType[l][1]) l--;
vector<vector<ll>> dp (r - m + 2, vector<ll>(m - l + 1, M));
if (l == 0) dp[0][0] = 0;
else dp[0][0] = best[l - 1];
//cout << l << " " << m << " " << r << " "<< (r - m + 2) << " " << (m - l + 1) << endl;
for (int i = l; i < m; i++)
{
dp[0][i - l + 1] = best[i];
}
for (int i = m; i <= r; i++)
{
for (int j = l; j < m; j++)
{
dp[i - m + 1][j - l + 1] = min({dp[i - m][j - l], dp[i - m + 1][j - l], dp[i - m][j - l + 1]}) + abs(byType[i][0] - byType[j][0]);
}
}
//cout << "Oj" << endl;
for (int i = m; i <= r; i++) best[i] = dp[i - m + 1][m - l];
}
}
return best[n + m - 1];
}
