#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
vvi G, W;
vi p, visited;
vector<vector<ll>> dp;
void dfs(int v, int par) {
visited[v] = true;
p[v] = par;
for (auto u : G[v]) {
if (u == par) continue;
if (visited[u]) continue;
dfs(u, v);
}
}
ll getDP(int v, bool needsGroup) {
if (dp[v][needsGroup] != -1) return dp[v][needsGroup];
if (p[v] != -1) {
if (G[v].size() == 1 && needsGroup) {
dp[v][needsGroup] = INT_MAX;
return dp[v][needsGroup];
} else if (G[v].size() == 1 && !needsGroup) {
dp[v][needsGroup] = 0;
return dp[v][needsGroup];
}
}
ll res = 0;
ll minX = INT_MAX;
for (int i = 0; i < G[v].size(); i++) {
int u = G[v][i];
if (u == p[v]) continue;
if (!needsGroup) {
res += min(getDP(u, 0)+W[v][i], getDP(u, 1));
}
else {
if (getDP(u, 1) == INT_MAX) {
res += getDP(u, 0)+W[v][i];
minX = 0;
} else {
res += getDP(u, 1);
minX = min(minX, getDP(u, 0)+W[v][i] - getDP(u, 1));
}
}
}
if (needsGroup) {
res += minX;
}
dp[v][needsGroup] = res;
return res;
}
ll min_total_length(vi r, vi b) {
int n = r.size(), m = b.size();
vi a;
vi left(n+m), right(n+m);
int lastR = -1, lastB = -1;
int idxA = 0, idxB = 0;
while (idxA < n || idxB < m) {
if (idxA < n && (idxB >= m || r[idxA] < b[idxB])) {
left[idxA+idxB] = lastB;
lastR = idxA+idxB;//r[idxA];
a.pb(r[idxA]);
idxA++;
} else {
left[idxA+idxB] = lastR;
lastB = idxA+idxB;//b[idxB];
a.pb(b[idxB]);
idxB++;
}
}
lastR = -1, lastB = -1;
idxA = n-1, idxB = m-1;
while (idxA >= 0 || idxB >= 0) {
if (idxA >= 0 && (idxB < 0 || r[idxA] > b[idxB])) {
right[idxA+idxB+1] = lastB;
lastR = idxA+idxB+1;//r[idxA];
idxA--;
} else {
right[idxA+idxB+1] = lastR;
lastB = idxA+idxB+1;//b[idxB];
idxB--;
}
}
G = vvi(n+m);
W = vvi(n+m);
map<pair<int, int>, int> doubleEdge;
for (int i = 0; i < n+m; i++) {
int d1 = left[i] != -1? a[i]-a[left[i]] : INT_MAX;
int d2 = right[i] != -1? a[right[i]]-a[i] : INT_MAX;
if ((d1 <= d2) && left[i] != -1 && doubleEdge.count({i, left[i]}) == 0) {
G[i].pb(left[i]);
W[i].pb(a[i]-a[left[i]]);
G[left[i]].pb(i);
W[left[i]].pb(a[i]-a[left[i]]);
doubleEdge[{i, left[i]}] = doubleEdge[{left[i], i}] = 1;
}
// cout << d1 << " " << d2 << endl;
if ((d2 <= d1) &&right[i] != -1 && doubleEdge.count({i, right[i]}) == 0) {
G[i].pb(right[i]);
W[i].pb(a[right[i]]-a[i]);
G[right[i]].pb(i);
W[right[i]].pb(a[right[i]]-a[i]);
doubleEdge[{i, right[i]}] = doubleEdge[{right[i], i}] = 1;
}
}
int k = 0;
for (int i = 0; i < n+m; i++) {
for (int j = 0; j < G[i].size(); j++) {
if (i >= G[i][j]) continue;
// cout << i << " " << G[i][j] << " " << W[i][j] << endl;
k += W[i][j];
}
}
// return k;
// for (int i = 0; i < n+m; i++) cout << right[i] << " ";
// cout << endl;
p = vi(n+m);
visited = vi(n+m);
for (int i = 0; i < n+m; i++) {
if (visited[i]) continue;
if (G[i].size() == 1) {
dfs(i, -1);
}
}
dp = vector<vector<ll>>(n+m, vector<ll>(2, -1));
int res = 0;
for (int i = 0; i < n+m; i++) {
if (dp[i][1] != -1) continue;
if (G[i].size() == 1) {
res += getDP(i, 1);
// cout << getDP(i, 1) << endl;
}
}
return res;
}
