#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;
struct state{
int ri,bi;
ll d;
double cost;
};
vector<double> c;
ll calc(vi &r, vi &b, double lambda){
auto cmp = [&](state a, state b){
ll av = a.d + a.cost * lambda;
ll bv = b.d + b.cost * lambda;
return av < bv;
};
vector<state> V;
for(state s{0,0,abs(r[0] - b[0]),0};1;V.clear()){
if(s.ri == r.size()-1 && s.bi == b.size()-1) return s.d;
if(s.ri < r.size()-1) V.push_back({s.ri+1,s.bi,s.d + abs(r[s.ri+1]-b[s.bi]),s.cost + c[s.ri]});
if(s.bi < b.size()-1) V.push_back(state{s.ri,s.bi+1,s.d + abs(r[s.ri]-b[s.bi+1]),s.cost + c[r.size()+s.bi]});
if(s.ri < r.size()-1 && s.bi < b.size()-1) V.push_back({s.ri+1,s.bi+1,s.d + abs(r[s.ri+1]-b[s.bi+1]),s.cost});
s = *min_element(V.begin(),V.end(),cmp);
}
}
ll min_total_length(vi r, vi b) {
int n = r.size(), m = b.size();
double lb = 0,rb = 1e18;
c.assign(m+n,0);
for(int i = 0;i < n+m;i++) c[i] = 1 + 1/double(3*(m+n)+i);
ll lv = calc(r,b,lb);
ll rv = calc(r,b,rb);
for(;lv != rv;){
double lm = (2*lb+rb)/3, rm = (2*rb+lb)/3;
ll lmv = calc(r,b,lm), rmv = calc(r,b,rm);
if(lmv < rmv){
rb = rm;
rv = rmv;
}
else{
lb = lm;
lv = lmv;
}
}
return lv;
}
