p=*0...gets.to_i;
f=->a{a==p[a]?a: p[a]=f[p[a]]}
a,b=$<.map{|s|s.split.map &:to_i}.transpose.map{|a|a.each_with_index.sort.each_cons(2).map{|(x,i),(y,j)|[y-x,i,j]}};
s=0;
(a+b).sort_by{|a,b,c|a}.each{|c,a,b|a,b=b,a if rand<0.5;(s+=c;p[f[a]]=f[b])if f[a]!=f[b]}
p s