#include <bits/stdc++.h>
#define f first
#include "wiring.h"
#define s second
#define BLUE 1
#define RED 2
#define N 100005
#define inf 2000000000000000000LL
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
ll n, m, r[N], b[N], dp[500][500];
ll custo(vector<int> esq, vector<int> dir)
{
if(esq.empty() || dir.empty()) return inf;
if(dir.back() < esq.front()) swap(esq, dir);
if(esq.back() > dir.front()) return inf;
ll sum_red = 0, sum_blue = 0;
for(auto x: esq) sum_red -= x;
for(auto x: dir) sum_blue += x;
sum_red += esq.size()*((ll)esq.back()), sum_blue -= dir.size()*((ll)dir.front());
return max(esq.size(), dir.size())*(dir.front() - esq.back()) + sum_blue + sum_red;
}
ll solve_greedy()
{
vector< pii > val;
for(int i = 1; i <= n; i++) val.push_back({r[i], BLUE});
for(int i = 1; i <= m; i++) val.push_back({b[i], RED});
sort(val.begin(), val.end());
int ini = 0, grp = 0, cnt = 0;
vector< int > aux[N], split[N];
vector< vector<int> > perf;
for(int i = 0; i < val.size(); i++)
{
if(i == val.size() - 1 || val[i].s != val[i + 1].s)
{
for(int j = ini; j <= i; j++) aux[ grp ].push_back(val[j].f);
grp ++;
ini = i + 1;
}
}
for(int i = 0; i < grp; i ++)
{
if(i == 0 || i == grp - 1) split[cnt] = (aux[i]), cnt ++;
else
{
if(aux[i].size() % 2 == 0)
{
for(int j = 0; j < aux[i].size(); j++)
{
if(j < aux[i].size()/2) split[cnt].push_back(aux[i][j]);
else split[cnt + 1].push_back(aux[i][j]);
}
if(split[cnt].empty() || split[cnt + 1].empty()) cnt --;
cnt += 2;
}
else
{
if(split[cnt - 1].size() >= ceil( aux[i + 1].size()/2.0 ))
{
for(int j = 0; j < aux[i].size(); j++)
{
if(j <= aux[i].size()/2) split[cnt].push_back(aux[i][j]);
else split[cnt + 1].push_back(aux[i][j]);
}
}
else
{
for(int j = 0; j < aux[i].size(); j++)
{
if(j < aux[i].size()/2) split[cnt].push_back(aux[i][j]);
else split[cnt + 1].push_back(aux[i][j]);
}
}
if(split[cnt].empty() || split[cnt + 1].empty()) cnt --;
cnt += 2;
}
}
}
ll sum = 0;
for(int i = 0; i < cnt; i++) if(!split[i].empty()) perf.push_back(split[i]);
for(int i = 0; i < perf.size() - 1; i++) sum += custo(perf[i], perf[i + 1]);
return sum;
}
ll solve(int i, int j)
{
if(!i && !j) return 0LL;
if(!i || !j) return inf;
if(dp[i][j] != -1) return dp[i][j];
return dp[i][j] = min(solve(i - 1, j), min(solve(i, j - 1), solve(i - 1, j - 1))) + abs(r[i] - b[j]);
}
ll dp2[N][70], cnt;
map<int, int> mapa;
int pos[N][2];
ll solve2(int i, int j)
{
if(!i && !j) return 0LL;
if(!i || !j || (abs(pos[i][0] - pos[j][1]) > 20)) return inf;
int dj = 21 + pos[i][0] - pos[j][1];
if(dp2[i][dj] != -1) return dp2[i][dj];
return dp2[i][dj] = min(solve2(i - 1, j), min(solve2(i, j - 1), solve2(i - 1, j - 1))) + abs(r[i] - b[j]);
}
ll min_total_length(vector<int> esq, vector<int> dir)
{
n = esq.size(), m = dir.size();
vector<int> all;
for(int i = 1; i <= n; i++) r[i] = esq[i - 1], all.push_back(esq[i - 1]);
for(int i = 1; i <= m; i++) b[i] = dir[i - 1], all.push_back(dir[i - 1]);
sort(all.begin(), all.end());
for(int i = 0; i < all.size(); i++)
{
if(!mapa[all[i]]) mapa[all[i]] = ++cnt;
}
for(int i = 1; i <= n; i++) pos[i][0]= mapa[r[i]];
for(int j = 1; j <= m; j++) pos[j][1] = mapa[b[j]];
memset(dp, -1, sizeof dp);
memset(dp2, -1, sizeof dp2);
if(esq.back() < dir.front()) return custo(esq, dir);
if(n <= 1000) return solve(n, m);
return min(solve2(n, m), solve_greedy());
}
