#include "wiring.h"
#include "bits/stdc++.h"
using namespace std;
#define forR(i, x) for(int i = 0; i < (x); ++i)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
const ll INF = 1e17;
struct grp{
char ty;
vi pos;
};
long long min_total_length(std::vector<int> r, std::vector<int> b) {
int n = r.size(), m = b.size();
vector<grp> gps;
int api=0, bpi=0;
while(api < n || bpi < m) {
if(api < n && (bpi == m || r[api] < b[bpi])) {
gps.push_back({'r', {}});
while(api < n && (bpi == m || r[api] < b[bpi])) {
gps.back().pos.push_back(r[api]);
++api;
}
} else {
gps.push_back({'b', {}});
while(bpi < m && (api == n || r[api] > b[bpi])) {
gps.back().pos.push_back(b[bpi]);
++bpi;
}
}
}
int l = gps.size();
vi cnt(l);
forR(i, l) cnt[i] = gps[i].pos.size();
vvll dp(l);
forR(i, l) dp[i].resize(cnt[i] + 1);
forR(i, l) {
if(i == 0) {
forR(j, cnt[i]) dp[i][j] = INF;
dp[i][cnt[i]] = 0;
} else {
ll sam = INF;
vector<ll> aCh(cnt[i-1] + 1), pm(cnt[i-1] + 1);
ll totRig = 0;
forR(las, cnt[i-1] + 1) {
if(las > 0) totRig += gps[i-1].pos.back() - gps[i-1].pos[cnt[i-1] - las];
ll cTot = dp[i-1][las] + totRig;
cTot += (ll) las * (gps[i].pos.front() - gps[i-1].pos.back());
aCh[las] = cTot;
}
pm[cnt[i-1]] = aCh[cnt[i-1]];
for(int j = cnt[i-1] - 1; j >= 0; --j) pm[j] = min(pm[j+1], aCh[j]);
ll bckTot = 0;
forR(bck, cnt[i] + 1) {
if(bck > 0) bckTot += gps[i].pos[bck-1] - gps[i].pos.front();
if(bck <= cnt[i-1]) {
sam = min(sam, aCh[bck] - (ll) bck * (gps[i].pos.front() - gps[i-1].pos.back()));
}
int fwd = cnt[i] - bck;
dp[i][fwd] = sam + bckTot + (ll) bck * (gps[i].pos.front() - gps[i-1].pos.back());
if(bck + 1 <= cnt[i-1]) {
dp[i][fwd] = min(dp[i][fwd], pm[bck + 1] + bckTot);
}
}
}
}
return dp[l-1][0];
}
