#include "wiring.h"
#include <bits/stdc++.h>
#define ll long long
#define inf 1e17
#define dbg(x) cerr << #x << ' ' << x << endl;
using namespace std;
vector<ll> p;
vector<ll> a;
vector<bool> b;
ll n, m;
ll sum(ll l, ll r)
{
ll sm=p[r];
if(l > 0) sm-=p[l-1];
return sm;
}
ll l3iba(ll l, ll r, ll x, ll y)
{
ll sm=sum(x,y)-sum(l,r);
ll sz1=(r-l+1);
ll sz2=y-x+1;
if(sz2 > sz1)
{
sm-=a[r]*(sz2-sz1);
}
else
{
sm+=a[x]*(sz1-sz2);
}
return sm;
}
long long min_total_length(std::vector<int> r, std::vector<int> bro)
{
n=r.size();
m=bro.size();
vector<pair<ll,ll>> merged;
for (int i=0;i<n;i++)
{
merged.push_back({r[i],0});
}
for (int i=0;i<m;i++)
{
merged.push_back({bro[i],1});
}
sort(merged.begin(),merged.end());
for (int i=0;i<n+m;i++)
{
a.push_back(merged[i].first);
b.push_back(merged[i].second);
}
p.resize(n+m);
for (int i=0;i<n+m;i++)
{
p[i]=a[i];
if(i>0)p[i]+=p[i-1];
}
vector<ll> dp(n+m,inf);
ll b1=-1;
ll b2=-1;
for (int i=0;i<m+n;i++)
{
if(i!=0 && b[i]!=b[i-1])
{
b1=i-1;
b2=i;
}
if(b1==-1 || b2==-1)
{
dp[i]=inf;
}
else
{
for (int j=b1;j>=0 && b[j]!=b[i];j--)
{
ll x=0;
if(j>0) x=dp[j-1];
dp[i]=min(dp[i],l3iba(j,b1,b2,i)+x);
}
}
}
return dp.back();
// return l3iba(0,n-1,n,m+n-1);
}
