#include <bits/stdc++.h>
#include "wiring.h"
#define DIM 200010
#define INF 2000000000000000000LL
using namespace std;
set <pair<int,long long> > L[DIM];
long long dp[DIM][2];
int f[DIM],Left0[DIM],Left1[DIM],Right0[DIM],Right1[DIM];
pair <int,int> v[DIM];
int modul (int n){
return max (n,-n);
}
void add_edge (int x, int y, long long cost){
L[x].insert(make_pair(y,cost));
L[y].insert(make_pair(x,cost));
//cout<<x<<" "<<y<<" "<<cost<<endl;
}
void dfs (int nod, int tata){
int ok = 0;
for (auto it : L[nod]){
int vecin = it.first;
if (vecin != tata){
ok = 1;
dfs (vecin,nod);
}}
if (!ok){
f[nod] = 1;
dp[nod][1] = INF;
} else {
/// dp[nod][0/1] - costul minim daca il am pe nod cuplat sau nu
/// daca nod e legat de o frunza nu pot sa am dp[nod][0]
int ok = 0;
for (auto it : L[nod]){
int vecin = it.first;
if (vecin == tata)
continue;
if (f[vecin]){
ok = 1;
break;
}}
if (ok){
dp[nod][0] = INF;
for (auto it : L[nod]){
int vecin = it.first, cost = it.second;
if (vecin == tata)
continue;
dp[nod][1] += min (dp[vecin][1], dp[vecin][0] + cost);
}
} else {
/// pot sa calculez ambele stari
for (auto it : L[nod]){
int vecin = it.first, cost = it.second;
if (vecin == tata)
continue;
dp[nod][0] += dp[vecin][1];
}
/// dp[nod][1] -> trb sa ma asigur ca va fi legat macar de un fiu!!
int ap = 0;
for (auto it : L[nod]){
int vecin = it.first, cost = it.second;
if (vecin == tata)
continue;
if (dp[vecin][0] + cost <= dp[vecin][1]){
dp[nod][1] += dp[vecin][0] + cost;
ap = 1;
} else dp[nod][1] += dp[vecin][1];
}
if (!ap){
long long mini = INF;
for (auto it : L[nod]){
int vecin = it.first, cost = it.second;
if (vecin == tata)
continue;
mini = min (mini,dp[nod][1] - dp[vecin][1] + dp[vecin][0] + cost);
}
dp[nod][1] = mini;
}}}}
long long min_total_length(vector<int> r, vector<int> b) {
int k = 0, i;
for (auto it : r)
v[++k] = make_pair(it,0);
for (auto it : b)
v[++k] = make_pair(it,1);
sort (v+1,v+k+1);
for (i=1;i<=k;i++){
if (v[i].second == 0){
Left0[i] = i;
Left1[i] = Left1[i-1];
} else {
Left0[i] = Left0[i-1];
Left1[i] = i;
}
}
for (i=k;i;i--){
if (v[i].second == 0){
Right0[i] = i;
Right1[i] = Right1[i+1];
} else {
Right0[i] = Right0[i+1];
Right1[i] = i;
}
}
for (i=1;i<=k;i++){
if (v[i].second == 0){
long long dist_left = INF, dist_right = INF;
if (Left1[i])
dist_left = modul (v[i].first - v[Left1[i]].first);
if (Right1[i])
dist_right = modul (v[i].first - v[Right1[i]].first);
if (dist_left <= dist_right)
add_edge (i,Left1[i],dist_left);
if (dist_right <= dist_left)
add_edge (i,Right1[i],dist_right);
} else {
long long dist_left = INF, dist_right = INF;
if (Left0[i])
dist_left = modul (v[i].first - v[Left0[i]].first);
if (Right0[i])
dist_right = modul (v[i].first - v[Right0[i]].first);
if (dist_left <= dist_right)
add_edge (i,Left0[i],dist_left);
if (dist_right <= dist_left)
add_edge (i,Right0[i],dist_right);
}
}
dfs (1,0);
return dp[1][1];
}
