#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll INF = 1000000000000000000LL;
ll n, m, q, k, x, y, a, c;
long long min_total_length(std::vector<int> r, std::vector<int> b) {
n = r.size();
m = b.size();
vector< pair<ll, ll> > vec;
for (int i : r) {
vec.push_back({i, 1});
}
for (int i : b) {
vec.push_back({i, 2});
}
sort(vec.begin(), vec.end());
set<ll> st;
for (int i = 0; i < n + m; i++) {
if (i != 0 && vec[i].second != vec[i - 1].second) {
st.insert(vec[i].first);
}
if (i != n + m - 1 && vec[i].second != vec[i + 1].second) {
st.insert(vec[i].first);
}
}
set< pair<ll, pair<ll, ll> > > two, one;
vector<bool> used1(n), used2(m);
for (int i = 0; i < n; i++) {
if (st.count(r[i])) {
continue;
}
if (r[i] <= b[b.size() - 1]) {
ll x = lower_bound(b.begin(), b.end(), r[i]) - b.begin();
two.insert({abs(r[i] - b[x]), {i, x}});
}
if (r[i] >= b[0]) {
ll x = (--upper_bound(b.begin(), b.end(), r[i])) - b.begin();
two.insert({abs(r[i] - b[x]), {i, x}});
}
}
for (int i = 0; i < m; i++) {
if (st.count(b[i])) {
continue;
}
if (b[i] <= r[r.size() - 1]) {
ll x = lower_bound(r.begin(), r.end(), b[i]) - r.begin();
two.insert({abs(r[x] - b[i]), {x, i}});
}
if (b[i] >= r[0]) {
ll x = (--upper_bound(r.begin(), r.end(), b[i])) - r.begin();
two.insert({abs(r[x] - b[i]), {x, i}});
}
}
// for (auto i : two) {
// cout << i.first << ' ' << i.second.first << ' ' << i.second.second << '\n';
// }
// cout << '\n';
ll ans = 0;
while (two.size() > 0 || one.size() > 0) {
pair<ll, ll> p1 = {-1, -1}, p2 = {-1, -1};
while (!two.empty() && p2.first == -1) {
p2 = (*two.begin()).second;
two.erase({abs(r[p2.first] - b[p2.second]), p2});
if (used1[p2.first] && used2[p2.second]) {
p2 = {-1, -1};
continue;
}
if (used1[p2.first] || used2[p2.second]) {
one.insert({abs(r[p2.first] - b[p2.second]), p2});
p2 = {-1, -1};
continue;
}
break;
}
while (!one.empty() && p1.first == -1) {
p1 = (*one.begin()).second;
one.erase({abs(r[p1.first] - b[p1.second]), p1});
if (used1[p1.first] && used2[p1.second]) {
p1 = {-1, -1};
continue;
}
break;
}
if (p1.first == -1 && p2.first == -1) {
break;
}
// cout << p1.first << ' ' << p1.second << '\n';
// cout << p2.first << ' ' << p2.second << '\n';
ll a1 = (p1.first == -1 ? INF : abs(r[p1.first] - b[p1.second]));
a1 *= 2;
ll a2 = (p2.first == -1 ? INF : abs(r[p2.first] - b[p2.second]));
// cout << min(a1 / 2, a2) << '\n';
// cout << '\n';
if (a2 <= a1) {
ans += a2;
used1[p2.first] = 1;
used2[p2.second] = 1;
}
else {
ans += a1 / 2;
used1[p1.first] = 1;
used2[p1.second] = 1;
}
}
// for (int i = 0; i < n; i++) {
// cout << used1[i] << ' ';
// }
// cout << '\n';
// for (int i = 0; i < m; i++) {
// cout << used2[i] << ' ';
// }
// cout << '\n';
for (int i = 0; i < n; i++) {
if (r[i] <= b[b.size() - 1]) {
ll x = lower_bound(b.begin(), b.end(), r[i]) - b.begin();
if (!used1[i] && !used2[x]) {
two.insert({abs(r[i] - b[x]), {i, x}});
}
else if (!used1[i] || !used2[x]) {
one.insert({abs(r[i] - b[x]), {i, x}});
}
}
if (r[i] >= b[0]) {
ll x = (--upper_bound(b.begin(), b.end(), r[i])) - b.begin();
if (!used1[i] && !used2[x]) {
two.insert({abs(r[i] - b[x]), {i, x}});
}
else if (!used1[i] || !used2[x]) {
one.insert({abs(r[i] - b[x]), {i, x}});
}
}
}
for (int i = 0; i < m; i++) {
if (b[i] <= r[r.size() - 1]) {
ll x = lower_bound(r.begin(), r.end(), b[i]) - r.begin();
if (!used1[x] && !used2[i]) {
two.insert({abs(r[x] - b[i]), {x, i}});
}
else if (!used1[x] || !used2[i]) {
one.insert({abs(r[x] - b[i]), {x, i}});
}
}
if (b[i] >= r[0]) {
ll x = (--upper_bound(r.begin(), r.end(), b[i])) - r.begin();
if (!used1[x] && !used2[i]) {
two.insert({abs(r[x] - b[i]), {x, i}});
}
else if (!used1[x] || !used2[i]) {
one.insert({abs(r[x] - b[i]), {x, i}});
}
}
}
// for (auto i : two) {
// cout << i.first << ' ' << i.second.first << ' ' << i.second.second << '\n';
// }
// cout << '\n';
while (two.size() > 0 || one.size() > 0) {
// for (int i = 0; i < n; i++) {
// cout << used1[i] << ' ';
// }
// cout << '\n';
// for (int i = 0; i < m; i++) {
// cout << used2[i] << ' ';
// }
// cout << '\n';
// cout << '\n';
pair<ll, ll> p1 = {-1, -1}, p2 = {-1, -1};
while (!two.empty() && p2.first == -1) {
p2 = (*two.begin()).second;
two.erase({abs(r[p2.first] - b[p2.second]), p2});
if (used1[p2.first] && used2[p2.second]) {
p2 = {-1, -1};
continue;
}
if (used1[p2.first] || used2[p2.second]) {
one.insert({abs(r[p2.first] - b[p2.second]), p2});
p2 = {-1, -1};
continue;
}
break;
}
while (!one.empty() && p1.first == -1) {
p1 = (*one.begin()).second;
one.erase({abs(r[p1.first] - b[p1.second]), p1});
if (used1[p1.first] && used2[p1.second]) {
p1 = {-1, -1};
continue;
}
break;
}
if (p1.first == -1 && p2.first == -1) {
break;
}
// cout << p1.first << ' ' << p1.second << '\n';
// cout << p2.first << ' ' << p2.second << '\n';
ll a1 = (p1.first == -1 ? INF : abs(r[p1.first] - b[p1.second]));
a1 *= 2;
ll a2 = (p2.first == -1 ? INF : abs(r[p2.first] - b[p2.second]));
// cout << min(a1 / 2, a2) << '\n';
// cout << '\n';
if (a2 <= a1) {
ans += a2;
used1[p2.first] = 1;
used2[p2.second] = 1;
if (p1.first != -1) {
one.insert({a1 / 2, p1});
}
}
else {
ans += a1 / 2;
used1[p1.first] = 1;
used2[p1.second] = 1;
if (p2.first != -1) {
two.insert({a2, p2});
}
}
}
return ans;
}
