#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<bool> vb;
typedef tuple<ll,ll,ll> PP;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define fi first
#define se second
#define pb emplace_back
#define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
template<class T> void out(T a){cout<<a<<endl;}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<endl;}
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
const ll inf=1001001001001001001;
#include "wiring.h"
long long min_total_length1(std::vector<int> r, std::vector<int> b) {
vp v;
rep(i,r.size())v.pb(r[i],0);
rep(i,b.size())v.pb(b[i],1);
sort(all(v));
ll n=v.size();
vi dp(n+1,inf);
dp[0]=0;
rep(i,n)REP(j,i+1,n+1){
vi dif;
REP(k,i,j-1)if(v[k].se!=v[k+1].se)dif.pb(k);
if(dif.size()!=1)continue;
ll sum=0;
REP(k,i,dif[0]+1)sum-=v[k].fi;
REP(k,dif[0]+1,j)sum+=v[k].fi;
sum+=max(0ll,(j-dif[0]-1)-(dif[0]+1-i))*(-v[dif[0]].fi);
sum+=max(0ll,-(j-dif[0]-1)+(dif[0]+1-i))*v[dif[0]+1].fi;
rep(t,j+1)chmin(dp[t],dp[i]+sum);
}
return dp[n];
}
long long min_total_length(std::vector<int> r, std::vector<int> b) {
vp v;
rep(i,r.size())v.pb(r[i],0);
rep(i,b.size())v.pb(b[i],1);
sort(all(v));
vector<pair<vi,ll>> al;
for(auto x:v){
if(al.size()==0||al.back().se!=x.se)al.pb(vi{x.fi},x.se);
else al.back().fi.pb(x.fi);
}
vi dp(al[0].fi.size()+1,inf);dp[0]=0;
REP(i,1,al.size()){
vi ndp(al[i].fi.size(),inf);
ll mi=inf,rui=0;
rep(j,al[i].fi.size()){
if(j<al[i-1].fi.size()){
ll tmp=al[i-1].fi[al[i-1].fi.size()-j-1];
rui-=tmp;
chmin(mi,dp[al[i-1].fi.size()-j-1]+rui+al[i-1].fi.back()*j);
}
chmin(ndp[j],mi-al[i-1].fi.back()*j);
}
mi=inf;rui=0;
rep(j,al[i-1].fi.size())rui-=al[i-1].fi[j];
rep(j,al[i-1].fi.size()){
chmin(mi,dp[j]+rui+(ll)(al[i-1].fi.size()-j)*al[i].fi[0]);
rui+=al[i-1].fi[j];
if(al[i-1].fi.size()-j-1<al[i].fi.size()){
chmin(ndp[al[i-1].fi.size()-j-1],mi-(ll)(al[i-1].fi.size()-j)*al[i].fi[0]);
}
}
rui=0;
rep(j,al[i].fi.size()){
rui+=al[i].fi[j];
ndp[j]+=rui;
}
if(i==al.size()-1)return ndp.back();
vi nndp(al[i].fi.size()+1);
nndp[0]=dp.back();
rep(j,ndp.size())nndp[j+1]=ndp[j];
for(int j=nndp.size()-1;j>0;j--)chmin(nndp[j-1],nndp[j]);
dp=nndp;
}
}
/*
int main(){
rep(tt,1000){
vector<int> a,b;
ll n=rand()%4+1,m=rand()%4+1;
rep(i,n)a.pb(rand()%10);
rep(i,m)b.pb(rand()%10);
dupli(a);dupli(b);
ll r1=min_total_length(a,b);
ll r2=min_total_length1(a,b);
if(r1!=r2){
out(tt);
outv(a);outv(b);
out(r1);out(r2);
break;
}
}
}
*/
