#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
int Nr, Nb;
std::vector<long long> R;
std::vector<long long> B;
std::vector<long long> Bclose;
std::vector<long long> Rclose;
vector<map<long long, int>> mem;
long long int dp(int r, int b){
if (r == Nr && b == Nb){
return 0;
}
if (mem[r][b])
return mem[r][b];
if (r == Nr){
mem[r][b] = dp(r, b + 1) + Bclose[b];
return mem[r][b];
}
if (b == Nb){
mem[r][b] = dp(r + 1, b) + Bclose[r];
return mem[r][b];
}
if (R[r] < B[b]){
mem[r][b] = min(dp(r + 1, b + 1) + B[b] - R[r], dp(r + 1, b) + Rclose[r]);
}else{
mem[r][b] = min(dp(r + 1, b + 1) + R[r] - B[b], dp(r, b + 1) + Bclose[b]);
}
return mem[r][b];
}
long long min_total_length(std::vector<int> r, std::vector<int> b) {
Nr = r.size();
Nb = b.size();
R.resize(Nr);
B.resize(Nb);
Rclose.resize(Nr);
Bclose.resize(Nb);
int j = 0;
for (int i = 0; i < Nr; i++){
R[i] = r[i];
}
for (int i = 0; i < Nb; i++){
B[i] = b[i];
}
for (int i = 0; i < Nr + Nb; i++){
if ((i - j != Nr) && (j == Nb || r[i - j] < b[j])){
if (j && j < Nb){
Rclose[i - j] = min(b[j] - r[i - j], r[i - j] - b[j - 1]);
}else if (j){
Rclose[i - j] = r[i - j] - b[j - 1];
}else{
Rclose[i - j] = b[j] - r[i - j];
}
}else{
if (i - j && i - j < Nr){
Bclose[j] = min(r[i - j] - b[j], b[j] - r[i - j - 1]);
}else if (i - j){
Bclose[j] = b[j] - r[i - j - 1];
}else{
Bclose[j] = r[i - j] - b[j];
}
j++;
}
}
mem.resize(Nr + 1);
return dp(0, 0);
}
