#include "wiring.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <set>
typedef long long llong;
const int MAXN = 200000 + 10;
const llong LLINF = 1e18;
const int INF = 1e9;
int n, m;
struct SegmentTree
{
llong tree[4*MAXN];
void update(int l, int r, int node, int queryPos, llong queryValue)
{
if (l == r)
{
tree[node] = queryValue;
return;
}
int mid = (l + r) / 2;
if (queryPos <= mid) update(l, mid, 2*node, queryPos, queryValue);
else update(mid + 1, r, 2*node + 1, queryPos, queryValue);
tree[node] = std::min(tree[2*node], tree[2*node + 1]);
}
llong query(int l, int r, int node, int queryL, int queryR)
{
if (queryL <= l && r <= queryR)
{
return tree[node];
}
llong res = LLINF;
int mid = (l + r) / 2;
if (queryL <= mid) res = std::min(res, query(l, mid, 2*node, queryL, queryR));
if (mid + 1 <= queryR) res = std::min(res, query(mid + 1, r, 2*node + 1, queryL, queryR));
return res;
}
void update(int pos, llong val)
{
update(1, n + m + 1, 1, pos, val);
}
llong query(int l, int r)
{
return query(1, n + m + 1, 1, l, r);
}
};
llong dp[MAXN];
llong suff[MAXN];
llong prefix[MAXN];
SegmentTree leftTree; // left is longer
SegmentTree rightTree; // right is longer
std::pair <int,bool> a[MAXN];
int inBucket[MAXN];
int right[MAXN];
int left[MAXN];
llong min_total_length(std::vector <int> R, std::vector <int> B)
{
n = R.size();
m = B.size();
for (int i = 1 ; i <= n ; ++i)
{
a[i] = {R[i - 1], false};
}
for (int i = 1 ; i <= m ; ++i)
{
a[n + i] = {B[i - 1], true};
}
std::sort(a + 1, a + 1 + n + m);
a[0].second = a[1].second ^ 1;
int cnt = 0;
for (int i = 1 ; i <= n + m ; ++i)
{
if (a[i].second == a[i - 1].second)
{
right[cnt] = i;
} else
{
cnt++;
left[cnt] = right[cnt] = i;
}
inBucket[i] = cnt;
}
for (int i = 1 ; i <= n + m ; ++i)
{
prefix[i] = prefix[i - 1] + a[i].first;
}
leftTree.update(1, -a[left[2]].first);
rightTree.update(1, -a[right[1]].first);
for (int i = 1 ; i <= n + m ; ++i)
{
if ((i > 1 && inBucket[i] != inBucket[i - 1]) || (i > 2 && inBucket[i - 2] != inBucket[i - 1]))
{
for (int j = i - 2 ; j >= left[inBucket[i - 2]] ; --j)
{
dp[j] = std::min(dp[j], dp[j + 1]);
}
for (int j = left[inBucket[i - 2]] ; j < i ; ++j)
{
leftTree.update(j + 1, prefix[j] + dp[j] - 1LL * (j + 1) * a[left[inBucket[j + 1] + 1]].first);
rightTree.update(j + 1, prefix[j] + dp[j] - 1LL * (j + 1) * a[right[inBucket[j + 1]]].first);
}
dp[i] = 0;
}
if (inBucket[i] == 1)
{
dp[i] = LLINF;
} else
{
int prevL = left[inBucket[i] - 1];
int prevR = right[inBucket[i] - 1];
if (i - prevR >= prevR - prevL + 1)
{
dp[i] = rightTree.query(prevL, prevR) + 1LL * (2 * prevR + 1 - i) * a[prevR].first;
} else
{
int equalPos = prevR - (i - prevR - 1);
dp[i] = rightTree.query(equalPos, prevR) + 1LL * (2 * prevR + 1 - i) * a[prevR].first;
dp[i] = std::min(dp[i], leftTree.query(prevL, equalPos - 1) + 1LL * (2 * prevR + 1 - i) * a[prevR + 1].first);
}
dp[i] += prefix[i] - 2 * prefix[prevR];
}
}
return dp[n + m];
}
