#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pi;
typedef pair<pi,ll> pil;
ll min_total_length(vi r, vi b) {
int n = r.size(), m = b.size();
vl rm(n),bm(m);
for(int i = 0,j = 0;i < n;i++){
for(;j < m;j++) if(j < m-1 && abs(r[i] - b[j]) < abs(r[i] - b[j+1])) break;
rm[i] = abs(r[i] - b[j]);
}
for(int i = 0,j = 0;i < m;i++){
for(;j < n-1;j++) if(j < n-1 && abs(r[j] - b[i]) < abs(r[j+1] - b[i])) break;
bm[i] = abs(r[j] - b[i]);
}
vl rs(n+1,0),bs(m+1,0);
inclusive_scan(rm.rbegin(),rm.rend(),rs.rbegin()+1);
inclusive_scan(bm.rbegin(),bm.rend(),bs.rbegin()+1);
auto cmp = [&](pil a, pil b){
ll av = a.second + max(rs[a.first.first + 1],bs[a.first.second + 1]);
ll bv = b.second + max(rs[b.first.first + 1],bs[b.first.second + 1]);
return av > bv;
};
priority_queue<pil,vector<pil>,decltype(cmp)> pq(cmp);
pq.push({{0,0},abs(r[0] - b[0])});
set<pi> S;
for(;1;){
pil t = pq.top();
int ri = t.first.first, bi = t.first.second;
ll d = t.second;
pq.pop();
if(S.count({ri,bi})) continue;
S.insert({ri,bi});
if(ri == r.size()-1 && bi == b.size()-1) return d;
if(ri < r.size()-1) pq.push({{ri+1,bi},d + abs(r[ri+1]-b[bi])});
if(bi < b.size()-1) pq.push({{ri,bi+1},d + abs(r[ri]-b[bi+1])});
if(ri < r.size()-1 && bi < b.size()-1) pq.push({{ri+1,bi+1},d + abs(r[ri+1]-b[bi+1])});
}
return -1;
}
