#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
/**
* Maryamga simlar loyihasini ishlab chiqishda yordam beruvchi funksiya.
* Har bir nuqta kamida bitta qarama-qarshi rangli nuqtaga ulanishi shart.
*/
ll min_total_length(vector<int> r, vector<int> b) {
int n = r.size();
int m = b.size();
// Barcha nuqtalarni birlashtirib, tartiblaymiz
struct Point {
int pos, type;
};
vector<Point> p;
int i = 0, j = 0;
while (i < n || j < m) {
if (i < n && (j == m || r[i] < b[j])) {
p.push_back({r[i++], 0}); // 0 - qizil
} else {
p.push_back({b[j++], 1}); // 1 - ko'k
}
}
int total_n = p.size();
// Nuqtalarni bir xil rangli guruhlarga ajratamiz
vector<vector<int>> groups;
if (total_n > 0) {
vector<int> cur = {p[0].pos};
for (int k = 1; k < total_n; k++) {
if (p[k].type == p[k-1].type) {
cur.push_back(p[k].pos);
} else {
groups.push_back(cur);
cur = {p[k].pos};
}
}
groups.push_back(cur);
}
int num_groups = groups.size();
vector<ll> dp(total_n + 1, 0);
vector<ll> pref(total_n + 1, 0);
for (int k = 0; k < total_n; k++) pref[k+1] = pref[k] + p[k].pos;
// dp[i] - i-chi nuqtagacha bo'lgan minimal xarajat
int last_idx = 0;
vector<ll> prev_dp;
for (int g = 0; g < num_groups; g++) {
int cur_sz = groups[g].size();
int first_idx = last_idx;
last_idx += cur_sz;
if (g == 0) {
for (int k = 1; k <= cur_sz; k++) dp[k] = 1e18; // Birinchi guruhni bog'lab bo'lmaydi
prev_dp.assign(dp.begin(), dp.begin() + cur_sz + 1);
continue;
}
int prev_sz = groups[g-1].size();
int p_end = first_idx - 1;
int c_start = first_idx;
// DP o'tishlarini optimallashtirish uchun yordamchi massivlar
vector<ll> cost_left(prev_sz + 1), cost_right(prev_sz + 1);
for (int j = 0; j <= prev_sz; j++) {
ll val = dp[first_idx - j];
ll s = pref[first_idx] - pref[first_idx - j];
ll dist_to_gap = (ll)j * p[c_start].pos - s;
cost_left[j] = val + dist_to_gap;
ll dist_to_prev_end = (ll)j * p[p_end].pos - s;
cost_right[j] = val + dist_to_prev_end;
}
vector<ll> min_left(prev_sz + 2, 1e18), min_right(prev_sz + 2, 1e18);
for (int j = prev_sz; j >= 0; j--) min_left[j] = min(min_left[j+1], cost_left[j]);
for (int j = 0; j <= prev_sz; j++) min_right[j+1] = min(min_right[j], cost_right[j]);
ll cur_pref_sum = 0;
for (int i = 1; i <= cur_sz; i++) {
cur_pref_sum += p[c_start + i - 1].pos;
ll s_curr = cur_pref_sum - (ll)i * p[c_start].pos;
// i va j ulanishlari: j >= i yoki j < i holatlari
ll opt1 = min_left[i] + s_curr;
ll opt2 = min_right[i] + s_curr + (ll)i * (p[c_start].pos - p[p_end].pos);
dp[first_idx + i] = min(opt1, opt2);
}
}
return dp[total_n];
}
