/**
* user: ppavic
* fname: Patrik
* lname: Pavić
* task: wiring
* score: 100.0
* date: 2019-06-13 11:05:56.973728
*/
//#include "wiring.h"
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <unordered_map>
#define X first
#define Y second
#define PB push_back
using namespace std;
typedef long long ll;
typedef pair < int, int > pii;
typedef vector < int > vi;
typedef vector < pii > vp;
const int N = 3e5 + 500;
const int LOG = 18;
const ll INF = 1e18;
const int OFF = (1 << LOG);
ll prf[N];
map < int , ll > dp[N];
int n, L[N], R[N], G[N], rv[N];
vp v;
inline ll dis(int x,int y){
return v[y].X - v[x].X;
}
inline ll get(int x,int y){
if(x > y) return 0;
return prf[y] - (x ? prf[x - 1] : 0);
}
ll f(int i,int lst){
//printf("stanje %d %d G %d L %d R %d, rv %d\n", i, lst, G[i], L[i], R[i], rv[i]);
if(dp[i][lst] != 0)
return dp[i][lst] - 1;
if(i == n){
if(lst > 0 && i > 1)
return -1 + (dp[i][lst] = f(i, lst - 1) + dis(L[i - 1] - 1, L[i] - lst) + 1);
return -1 + (dp[i][lst] = (lst != 0) * INF + 1);
}
ll ret = INF;
if(lst > 0)
ret = min(ret, f(i, lst - 1) + dis(L[i] - lst, L[i]));
if(lst <= G[i])
ret = min(ret, f(i + 1, G[i] - lst) + get(L[i], L[i] + lst - 1) - get(L[i] - lst, L[i] - 1));
if(i > 1 && lst > 0)
ret = min(ret, f(i, lst - 1) + dis(L[i - 1] - 1, L[i] - lst));
return -1 + (dp[i][lst] = ret + 1);
}
ll min_total_length(vi r, vi b) {
for(int i = 0;i < N;i++) dp[i].clear();
ll S_r = 0, S_b = 0;
for(int x : r) v.PB({x, 1});
for(int x : b) v.PB({x, 0});
sort(v.begin(), v.end());
int l = 0, ll = 0, gr = 0;
for(int i = 0;i < v.size();i++){
prf[i] = (long long)(v[i].X) + (i ? prf[i - 1] : 0);
if(v[i].Y != l && i != 0){
if(gr)
rv[gr] = G[gr - 1] + rv[gr - 1];
G[gr] = i - ll;
L[gr] = ll;
R[gr++] = i - 1;
// printf("grupa %d : %d %d S %d\n", gr - 1, L[gr - 1], R[gr - 1], G[gr - 1]);
ll = i;
}
l = v[i].Y;
}
rv[gr] = G[gr - 1] + rv[gr - 1];
G[gr] = v.size() - ll; L[gr] = ll; R[gr] = v.size() - 1;
n = ++gr; L[n] = v.size();
//printf("grupa %d : %d %d S %d\n", gr - 1, L[gr - 1], R[gr - 1], G[gr - 1]);
return f(0, 0);
}
// ovo zakomentirati prilkom submita
/**
int main(){
int n, m, xx; scanf("%d%d", &n, &m);
vi v1, v2;
for(;n--;) scanf("%d", &xx), v1.PB(xx);
for(;m--;) scanf("%d", &xx), v2.PB(xx);
printf("%lld\n", min_total_length(v1, v2));
}
**/
