#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=100000000000000007;
const int N=200007,pot=1<<18;
ll seg[2*pot+7][3];
ll DP[N];
ll P[N],P1[N];
ll S[N],S1[N];
ll que(int v,int a,int b,int l,int r,int i)
{
if(a<=l&&b>=r) return seg[v][i];
if(r<a||l>b) return infl;
return min(que(2*v,a,b,l,(l+r)/2,i),que(2*v+1,a,b,(l+r)/2+1,r,i));
}
void ins(int v,ll x,int i)
{
v+=pot-1;
seg[v][i]=x;
while(v>1)
{
v/=2;
seg[v][i]=min(seg[2*v][i],seg[2*v+1][i]);
}
}
ll min_total_length(vector<int>r,vector<int>b)
{
vector<pair<ll,int>>V;
int n=sz(r),m=sz(b);
for(int i=0;i<n;i++) V.pb({r[i],0});
for(int i=0;i<m;i++) V.pb({b[i],1});
sort(all(V));
for(ll i=1;i<n+m;i++)
{
P[i]=P[i-1]+V[i].st-V[i-1].st;
P1[i]=P1[i-1]+(V[i].st-V[i-1].st)*i;
}
for(int i=n+m-1;i>0;i--)
{
S[i]=S[i+1]+V[i].st-V[i-1].st;
S1[i]=S1[i+1]+(V[i].st-V[i-1].st)*(n+m-i);
}
for(int i=1;i<2*pot;i++) seg[i][0]=infl,seg[i][1]=infl,seg[i][2]=infl;
int L=1,R=0;
ins(1,0,2);
for(int i=0;i<n+m;i++)
{
if(i>0&&V[i].nd!=V[i-1].nd)
{
L=R+1;
R=i;
for(int j=L;j<=R;j++)
{
ll X=P1[R-1]-P1[j-1]-(P[R-1]-P[j-1])*(j-1);
ll dp=que(1,j,i+1,1,pot,2);
ins(j,dp+X,0);
ins(j,dp+X+(V[R].st-V[R-1].st)*(R-j+1),1);
}
}
DP[i+1]=infl;
if(R>0)
{
ll k=i+1-R;
ll X=S1[R+1]-S1[i+1]-(S[R+1]-S[i+1])*(n+m-i-1);
DP[i+1]=min(DP[i+1],que(1,L,R-k+1,1,pot,1)+X);
DP[i+1]=min(DP[i+1],que(1,max((ll)L,R-k+2),R,1,pot,0)+X+k*(V[R].st-V[R-1].st));
}
ins(i+2,DP[i+1],2);
}
return DP[n+m];
}
/*
ll min_total_length1(vector<int>r,vector<int>b)
{
ll ans=0;
for(int i=1;i<sz(r);i++) ans+=(ll)(r[i]-r[i-1])*i;
for(int i=sz(b)-1;i>0;i--) ans+=(ll)(b[i]-b[i-1])*(sz(b)-i);
ans+=(ll)max(sz(r),sz(b))*(ll)(b[0]-r.back());
return ans;
}
int main()
{
int n=100,m=200;
cin>>n>>m;
int t=0;
vector<int>r,b;
for(int i=0;i<n;i++)
{
t+=rand()%10+1;
cin>>t;
r.pb(t);
cout<<t<<" ";
}
cout<<endl;
for(int i=0;i<m;i++)
{
t+=rand()%10+1;
cin>>t;
b.pb(t);
cout<<t<<" ";
}
cout<<endl;
cout<<min_total_length(r,b)<<endl;
return 0;
}*/
