#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
#define s second
#define f first
typedef long long ll;
ll min_total_length(vector<int> R, vector<int> B) {
const int n=R.size(),m=B.size();
vector<pair<ll,int>> pos;
for(auto it : R ){
pos.push_back({it, 0});
}
for(auto it: B){
pos.push_back({it, 1});
}
sort(pos.begin(),pos.end());
vector<vector<ll>> v={{pos[0].f}};
for(int i=1;i<n+m;i++){
if(pos[i].s==pos[i-1].s){
v.back().push_back(pos[i].f);
}
else {
v.push_back({pos[i].f});
}
}
vector<ll> p(v[0].size()+1, 1e15), pw(v[0].size()+1, 1e15);
p[0]=0;
for(int j=0;j<(int)v[0].size();j++){
p[0]+=v[0].back()-v[0][j];
}
pw[0]=p[0] + v[0].size() * (v[1][0]-v[0].back());
for(int i=1;i<=(int)v[0].size();i++){
pw[i]=min(pw[i-1], p[i]+((int)v[0].size()-i+1)*(v[1][0]-v[0].back()));
}
//~ for(int i=0;i<(int)v.size();i++){
//~ cout<<"vector " << i <<" : ";
//~ for(auto it:v[i])cout<<it<<' ';
//~ cout<<endl;
//~ }
//~ for(auto it:p)cout<<it<<" ";
//~ cout<<endl;
//~ for(auto it:pw) cout<<it<<" ";
//~ cout<<endl;
//~ cout<<endl;
for(int i=1;i<(int)v.size();i++){
vector<ll> cur(v[i].size()+1, 1e15);
ll tr=0, tl=0,a=v[i][0]-v[i-1].back();
for(int j=0;j<(int)v[i].size();j++) tr+=v[i].back()-v[i][j];
cur[0]=p.back();
//~ cout<<i<<endl;
for(int j=1;j<=(int)v[i].size();j++){
tr-=(v[i].back()-v[i][j-1]);
tl+=(v[i][j-1] - v[i][0]);
cur[j]=min(
((int)v[i-1].size()-j+1 >= 0 ? p[v[i-1].size()-j+1] : p[0])+j*a+tr+tl,
((int)v[i-1].size()-j >= 0 ? pw[v[i-1].size()-j]: (ll)1e15)+tr+tl
);
}
//~ printf("%d, dp values before cleaning: \n", i);
//~ for(auto it : cur)cout<<it<<" ";
//~ cout<<endl;
swap(cur, p);
//~ printf("i is %d, size is %d\n", i, (int)v[i].size());
for(int j=0;j<(int)v[i].size();j++){
//~ cout<<p[j]<<" "<<p[j+1]<<'\n';;
p[j]=min(p[j+1],p[j]);
}
vector<ll> npw(p.begin(),p.end());
//~ printf("%d, dp values after cleaning: \n", i);
//~ for(auto it : p)cout<<it<<" ";
//~ cout<<endl;
//~ for(auto it: npw)cout<<it<<' ';
//~ cout<<endl;
int na=(i==(int)v.size()-1? 0: v[i+1][0]-v[i].back());
npw[0]+=v[i].size() * na;
for(int j=1;j<=(int)v[i].size();j++){
npw[j]=min(npw[j-1], p[j]+((int)v[i].size()-j)*na);
}
for(int j=(int)v[i].size()-1;j>=0;j--){
p[j]=min(p[j+1], p[j]);
}
swap(npw, pw);
}
return p.back();
}
/*
4 2
1 2 9 12
4 7
4 5
1 2 3 7
0 4 5 9 10
1 4
5
1 2 7 8
3 3
1 3 5
2 4 6
*/
