/********************************************
Task: IOI17_WIRING
Link: https://oj.uz/problem/view/IOI17_wiring
********************************************/
#include <bits/stdc++.h>
#include "wiring.h"
#define fi first
#define se second
#define maxn 100005
using namespace std;
using ii = pair<int, int>;
template <class T> inline constexpr void cmin(T &x, const T &y) {if (x > y) x = y;}
int n, m, N;
ii a[2*maxn];
vector<vector<int> > v;
vector<vector<int64_t> > s;
int64_t dp[2][2*maxn];
int64_t solve() {
N = n+m;
sort(a, a + N);
for (int i2 = 0; i2 < N;) {
int i1 = i2;
vector<int> p(1, 0);
while (i2 < N && a[i2].se == a[i1].se) ++i2;
for (int i = i1; i < i2; i++) p.emplace_back(a[i].fi);
vector<int64_t> prefix_sum(int(p.size()), 0);
for (int i = 1; i < p.size(); i++) prefix_sum[i] = prefix_sum[i-1] + p[i];
v.emplace_back(p);
s.emplace_back(prefix_sum);
}
int sz = v.size();
dp[0][0] = 0;
for (int i = 1; i < v[0].size(); i++) dp[0][i] = LLONG_MAX/100;
for (int o = 1; o < sz; o++) {
int L = v[o-1].size()-1, R = v[o].size()-1,
u1 = (o&1), u2 = 1-u1;
int LIM = max(L, R);
vector<int64_t> prefix_sum = s[o-1];
vector<int64_t> prefix_min(LIM+2, LLONG_MAX/100), suffix_min(LIM+2, LLONG_MAX/100);
//suffix when L > R --> L-R must be connected to the first one of R
//prefix when L <= R --> R-L must be connected to the last one of L
for (int i = 0; i <= L; i++) {
int rr = L-i;
cmin(suffix_min[rr], dp[u2][i] + prefix_sum[i] - prefix_sum[L] + int64_t(rr) * v[o][1]);
cmin(prefix_min[rr], dp[u2][i] + prefix_sum[i] - prefix_sum[L] + int64_t(rr) * v[o-1][L]);
}
for (int i = 1; i <= LIM; i++) cmin(prefix_min[i], prefix_min[i-1]);
for (int i = LIM; i >= 0; i--) cmin(suffix_min[i], suffix_min[i+1]);
prefix_sum = s[o];
dp[u1][0] = dp[u2][L];
for (int i = 1; i <= R; i++) dp[u1][i] = min(prefix_sum[i] + suffix_min[i] - int64_t(i) * v[o][1],
prefix_sum[i] + prefix_min[i] - int64_t(i) * v[o-1][L]);
}
return dp[(sz-1)&1][v[sz-1].size()-1];
}
/*
4 5
1 2 3 7
0 4 5 9 10
10
*/
long long min_total_length(vector<int> r, vector<int> b) {
n = r.size(); m = b.size();
for (int i = 0; i < n; i++) a[i] = {r[i], 0};
for (int i = 0; i < m; i++) a[i+n] = {b[i], 1};
return solve();
}
