#include <bits/stdc++.h> #define L(i, j, k) for(int i = (j); i <= (k); i++) #define R(i, j, k) for(int i = (j); i >= (k); i--) #define ll long long #define sz(a) ((int) a.size()) #define all(a) a.begin(), a.end() #define vi vector<ll> #define pb emplace_back #define me(a, x) memset(a, x, sizeof(a)) #define fst first #define snd second #define ii pair<ll, ll> using namespace std; const int N=1e5+5; const ll inf=1e18; void chmin(ll &a,ll b){ a=min(a,b); } long long min_total_length(std::vector<int> r, std::vector<int> b) { int n=sz(r),m=sz(b); vector<ii> points; L(i,0,n-1){ points.pb(r[i],1); } L(i,0,m-1){ points.pb(b[i],0); } sort(all(points)); int nn=sz(points); vector<vi>blk; vi ar; int lst=points[0].snd; L(i,0,nn-1){ if(lst!=points[i].snd){ blk.pb(ar); ar.clear(); lst^=1; } ar.pb(points[i].fst); } blk.pb(ar); vector<vi>dp(sz(blk)); dp[0].resize(sz(blk[0])+1,0); L(i,1,sz(blk)-1){ dp[i].resize(sz(blk[i])+1,inf); ll diff=blk[i][0]-blk[i-1].back(),pf=0; dp[i][0]=dp[i-1].back(); if(i==sz(blk)-1&&sz(blk[i])==1){ ll sf=0,pf=0; L(r,0,sz(blk[i])-1)pf+=blk[i][r]-blk[i][0]; //~ cout<<diff<<endl; R(l,sz(blk[i-1]),1){ sf+=blk[i-1].back()-blk[i-1][l-1]; chmin(dp[i].back(),dp[i-1][l]+sz(blk[i])*diff+pf); break; } continue; } L(r,0,sz(blk[i])-1){ pf+=blk[i][r]-blk[i][0]; ll sf=0; R(l,sz(blk[i-1])-1,0){ sf+=blk[i-1].back()-blk[i-1][l]; chmin(dp[i][r+1],dp[i-1][l]+max(sz(blk[i-1])-l,r+1)*diff+pf+sf); } } } return dp.back().back(); } //~ int main() { //~ int n, m; //~ assert(2 == scanf("%d %d", &n, &m)); //~ vector<int> r(n), b(m); //~ for(int i = 0; i < n; i++) //~ assert(1 == scanf("%d", &r[i])); //~ for(int i = 0; i < m; i++) //~ assert(1 == scanf("%d", &b[i])); //~ long long res = min_total_length(r, b); //~ printf("%lld\n", res); //~ return 0; //~ }