#include <bits/stdc++.h>
#include "wiring.h"
#define ll long long
#define pii pair<int, int>
#define fir first
#define sec second
using namespace std;
const int mxN=100010;
const ll INF=1e18;
int N, M;
vector <int> R, B;
vector <pii> RR, BB;
vector <ll> pR, pB;
map <pii, ll> dp;
ll myabs(ll a) {return (a>0 ? a : -a);}
vector <pii> cr[2*mxN], cb[2*mxN];
ll sumR(int a, int b)
{
if(a==0) return pR[b];
else return pR[b]-pR[a-1];
}
ll sumB(int a, int b)
{
if(a==0) return pB[b];
else return pB[b]-pB[a-1];
}
ll f(int r, int b)
{
pii now=pii(r, b);
int nval=myabs(R[r]-B[b]);
if(dp.find(now)!=dp.end()) return dp[now];
if(r==N-1 && b==M-1) return dp[now]=nval;
ll ret=INF;
if(R[r]>B[b])
{
if(b==M-1) return dp[now]=f(r+1, b)+nval;
if(r<N-1)
{
if(R[r+1]>B[b+1])
{
int cidx=r-b+mxN;
int tmp=lower_bound(cr[cidx].begin(), cr[cidx].end(), now)-cr[cidx].begin();
assert(cr[cidx][tmp]==now);
tmp++;
if(tmp!=cr[cidx].size())
{
pii nxt=cr[cidx][tmp];
ret=min(ret, sumR(r, nxt.fir-1)-sumB(b, nxt.sec-1)+f(nxt.fir, nxt.sec));
}
}
else ret=min(ret, nval+f(r+1, b+1)), ret=min(ret, nval+f(r+1, b));
}
ret=min(ret, nval+f(r, b+1));
//printf("dp[%d, %d]=%lld\n", r, b, ret);
return dp[now]=ret;
}
else
{
if(r==N-1) return dp[now]=f(r, b+1)+nval;
if(b<M-1)
{
if(R[r+1]<B[b+1])
{
int cidx=r-b+mxN;
int tmp=lower_bound(cb[cidx].begin(), cb[cidx].end(), now)-cb[cidx].begin();
assert(cb[cidx][tmp]==now);
tmp++;
if(tmp!=cb[cidx].size())
{
pii nxt=cb[cidx][tmp];
ret=min(ret, sumB(b, nxt.sec-1)-sumR(r, nxt.fir-1)+f(nxt.fir, nxt.sec));
}
}
else ret=min(ret, nval+f(r+1, b+1)), ret=min(ret, nval+f(r, b+1));
}
ret=min(ret, nval+f(r+1, b));
//printf("dp[%d, %d]=%lld\n", r, b, ret);
return dp[now]=ret;
}
}
ll min_total_length(vector<int> r, vector<int> b) {
N=r.size(), M=b.size();
R=r; B=b;
pR.resize(N);
pB.resize(M);
pR[0]=R[0];
for(int i=1;i<N;i++) pR[i]=pR[i-1]+R[i];
pB[0]=B[0];
for(int i=1;i<M;i++) pB[i]=pB[i-1]+B[i];
for(int i=0;i<N;i++)
{
int pos=lower_bound(B.begin(), B.end(), R[i])-B.begin();
if(pos!=M) BB.emplace_back(i, pos);
if(pos!=0) RR.emplace_back(i, pos-1);
}
for(int i=0;i<M;i++)
{
int pos=lower_bound(R.begin(), R.end(), B[i])-R.begin();
if(pos!=N) RR.emplace_back(pos, i);
if(pos!=0) BB.emplace_back(pos-1, i);
}
sort(RR.begin(), RR.end());
sort(BB.begin(), BB.end());
RR.erase(unique(RR.begin(), RR.end()), RR.end());
BB.erase(unique(BB.begin(), BB.end()), BB.end());
/*printf("RR");
for(pii ele : RR) printf("(%d, %d) ", ele.fir, ele.sec);
printf("\nBB");
for(pii ele : BB) printf("(%d, %d) ", ele.fir, ele.sec);
printf("\n");*/
for(pii ele : RR) cr[mxN+ele.fir-ele.sec].push_back(ele);
for(pii ele : BB) cb[mxN+ele.fir-ele.sec].push_back(ele);
return f(0, 0);
}
/*
4 5
1 2 3 7
0 4 5 9 10
*/
