#include <bits/stdc++.h>
#include "wiring.h"
#define N 100005
#define inf 2000000000000000000LL
using namespace std;
typedef long long ll;
ll n, m, r[N], b[N], dp[500][500];
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 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 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 solve2(n, m);
}
