#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
#define prev previousguy
#define ll long long
#define maxn 100010
#define pii pair<int, int>
ll dp[2][maxn];
int prev, cur;
int n, m;
const ll inf = 1LL << 62;
vector<pii> stuff;
ll suf[maxn];
ll pref[maxn];
ll min_total_length(vector<int> r, vector<int> b) {
n = r.size();
m = b.size();
cur = 0; prev = 1;
for (int i = 0; i < n; i++) {
stuff.push_back(pii(r[i], 0));
}
for (int i = 0; i < m; i++) {
stuff.push_back(pii(b[i], 1));
}
sort(stuff.begin(), stuff.end());
int lastsize = -1;
for (int i = 0; i < n+m; i++) {
int cstart = i;
int cend = i;
while (cend < n + m - 1 && stuff[cend+1].second == stuff[cend].second)
++cend;
// cout << "group from " << cstart << " " << cend << endl;
swap(prev, cur);
int csize = cend - cstart+1;
if (lastsize == -1) {
dp[cur][0] = 0;
for (int j = 1; j <= csize; j++) dp[cur][j] = inf;
}
else {
ll gap = stuff[cstart].first - stuff[cstart-1].first;
// cout << "GAP: " << gap << endl;
int oend = cstart-1;
//do suffix for how many we take
suf[0] = 0;
for (int j = 1; j <= lastsize; j++) {
suf[j] = suf[j-1] + stuff[oend].first -
stuff[oend-j+1].first;
}
pref[0] = 0; //prefix for how many we take
for (int j = 1; j <= csize; j++) {
pref[j] = pref[j-1] + stuff[cstart+j-1].first -
stuff[cstart].first;
}
for (int j = 0; j <= csize; j++) {
dp[cur][j] = inf;
}
//do minimum from the left
ll curmin = inf;
for (int j = 0; j <= csize; j++) {
//consider taking less than me from the left to connect
if (lastsize - j >= 0)
curmin = min(curmin, dp[prev][lastsize-j] + suf[j]);
dp[cur][j] = min(dp[cur][j], curmin + pref[j] + gap*j);
// cout << " " << j << ": " << pref[j] <<
// " " << dp[cur][j] << " - " << curmin <<
// " suf: " << suf[j] << endl;
}
curmin = inf;
//below considers that previous #fixed is at least current fixed
for (int j = lastsize; j > csize; j--) {
//consider taking all but this many
curmin = min(curmin, j * gap + dp[prev][lastsize-j] +
suf[j]);
}
for (int j = csize; j >= 0; --j) {
if (lastsize - j >= 0) //j <= lastsize is same
curmin = min(curmin, j * gap + dp[prev][lastsize-j] +
suf[j]);
dp[cur][j] = min(dp[cur][j], curmin + pref[j]);
}
}
// cout << cstart << " to " << cend << endl;
// for (int j = 0; j <= csize; j++) {
// cout << " " << j << " : " << dp[cur][j] << endl;
// }
// cout << endl;
lastsize = csize;
i = cend;
}
return dp[cur][lastsize];
}
