#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
#define sig signed
#define int long long
#define arr array
#define vec vector
#define pii pair<int, int>
#define fir first
#define sec second
const int N = 5e3 + 5, INF = 1e18;
int n;
arr<pii, N> a;
vec<vec<int>> rng;
void rng_cmp() {
for (int i = 1; i <= n; i++) {
if (rng.empty() || a[i].sec != rng.back()[2]) rng.push_back({i, i, a[i].sec});
else rng.back()[1] = i;
}
}
int scr(int l1, int r1, int l2, int r2) {
int ans = 0;
for (int i = l1; i <= r1; i++) ans -= a[i].fir;
for (int i = l2; i <= r2; i++) ans += a[i].fir;
int sz1 = r1 - l1 + 1, sz2 = r2 - l2 + 1;
if (sz1 > sz2) ans += (sz1 - sz2) * a[l2].fir;
else ans -= (sz2 - sz1) * a[r1].fir;
return ans;
}
arr<int, N> dp;
void dp_cmp() {
for (int i = 1; i <= n; i++) {
dp[i] = INF;
vec<int> tr = {i, INF, INF};
int cr = upper_bound(rng.begin(), rng.end(), tr) - 1 - rng.begin();
if (cr == 0) continue;
int prv = cr - 1;
for (int j = rng[prv][0]; j <= rng[prv][1]; j++) {
dp[i] = min(dp[i], min(dp[j - 1], dp[j]) + scr(j, rng[prv][1], rng[cr][0], i));
}
// cout << i << ": " << dp[i] << endl;
}
}
struct Chck {
int n, m;
arr<int, N> a;
arr<int, N> b;
arr<arr<int, N>, N> dp;
void dp_cmp() {
for (int i = 1; i <= n + 1; i++) dp[i].fill(INF);
dp[n + 1][m + 1] = 0;
for (int i = n; i >= 1; i--) {
for (int j = m; j >= 1; j--) {
int cr = 0;
for (int k = i; k <= n; k++) {
cr += abs(a[k] - b[j]);
dp[i][j] = min(dp[i][j], cr + dp[k + 1][j + 1]);
}
cr = 0;
for (int k = j; k <= m; k++) {
cr += abs(b[k] - a[i]);
dp[i][j] = min(dp[i][j], cr + dp[i + 1][k + 1]);
}
}
}
}
int min_total_length(vec<sig> _a, vec<sig> _b) {
n = _a.size(), m = _b.size();
for (int i = 1; i <= n; i++) a[i] = _a[i - 1];
for (int i = 1; i <= m; i++) b[i] = _b[i - 1];
dp_cmp();
return dp[1][1];
}
} chck;
int min_total_length(vec<sig> _a0, vec<sig> _a1) {
n = _a0.size() + _a1.size();
for (int i = 1; i <= _a0.size(); i++) a[i] = {_a0[i - 1], 0};
for (int i = _a0.size() + 1; i <= n; i++) a[i] = {_a1[i - _a0.size() - 1], 1};
sort(a.begin() + 1, a.begin() + n + 1);
rng_cmp();
dp_cmp();
// for (int i = 1; i <= n; i++)
// cout << a[i].fir << " " << a[i].sec << '\n';
// for (vec<int> x : rng) {
// for (int y : x) cout << y << " ";
// cout << '\n';
// }
// int ans = dp[n];
// int chck_ans = chck.min_total_length(_a0, _a1);
// if (ans != chck_ans) {
// cout << "AHH" << endl;
// }
return dp[n];
}
