#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint INF = 1e18;
vector<vector<lint>> memo;
vector<vector<lint>> cluster;
vector<lint> G(1), D(1);
inline lint connect(int le, int ri) { // connect two points: le and ri
return (le <= 0)? INF : (D[ri] - D[ri - 1] - D[le] + D[le - 1]);
}
inline lint connect_all(int le, int mid, int ri) { // connect all points between le and ri, with mid as pivot (the last element of previous group)
return (le <= 0)? INF : (D[ri] - D[mid] - D[mid] + D[le - 1]);
}
inline int get_index(int group, lint plus_minus) {
return G[group] + plus_minus;
}
lint dp(int group, int previous_left) {
if (previous_left < 0) return INF;
if (memo[group][previous_left] != -1) return memo[group][previous_left];
lint &res = memo[group][previous_left];
res = INF;
/* connect leftmost unpaired point of previous group with leftmost popint of current group */
if (group < cluster.size() && previous_left > 0)
res = min(res, dp(group, previous_left - 1) + connect(get_index(group - 1, 1 - previous_left), get_index(group - 1, 1)));
/* connect leftmost unpaired point of previous group with rightmost point of the group before it */
if (group > 2 && previous_left > 0)
res = min(res, dp(group, previous_left - 1) + connect(get_index(group - 2, 0), get_index(group - 1, 1 - previous_left)));
/* connect all unpaired points in the previous group with the prefix of points in the current group */
if (group < cluster.size())
res = min(res, dp(group + 1, cluster[group].size() - previous_left) +
connect_all(get_index(group - 1, 1 - previous_left), get_index(group - 1, 0), get_index(group - 1, previous_left)));
/* base case: all pairs of wires are already connected */
if (group == cluster.size() && previous_left == 0)
res = 0;
return res;
}
lint min_total_length(vector<int> r, vector<int> b) {
int N = r.size() + b.size();
vector<pair<lint, char>> all_wires(N), red, blue;
for (auto i : r) red.push_back({i + 1, 'r'});
for (auto i : b) blue.push_back({i + 1, 'b'});
merge(red.begin(), red.end(), blue.begin(), blue.end(), all_wires.begin());
cluster.emplace_back();
cluster[0].emplace_back(0);
for (int i = 0; i < N; i++) {
int le = i;
while (i + 1 < N && all_wires[i + 1].second == all_wires[le].second) i++;
int ri = i;
cluster.emplace_back();
for (int j = le; j <= ri; j++) {
cluster.back().emplace_back(all_wires[j].first);
}
}
/* make DP table */
memo.resize(cluster.size() + 1);
for (int i = 1; i <= cluster.size(); i++) memo[i].assign(cluster[i - 1].size() + 1, -1);
/* G = prefix sum of group size, D = prefix sum of x-coordinates */
G[0] = D[0] = 0;
for (int i = 1; i < cluster.size(); i++) G.push_back(G.back() + cluster[i].size());
G.push_back(G.back());
for (int i = 1; i < cluster.size(); i++) for (auto j : cluster[i]) D.push_back(D.back() + j);
return dp(1, 0);
}
