#include <bits/stdc++.h>
#include "wiring.h"
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define inf 1000000000000007
#define N 1000005
using namespace std;
typedef long long ll;
typedef vector < ll > vi;
typedef pair < ll , ll > ii;
ll n, m, l1, r1, l2, r2, pre[N];
ii a[N], b[N];
ll dp[N];
ll f(int n, int m){
ll &r = dp[n];
if(r != -1)
return r;
return r;
}
ll min_total_length(vector < int > r, vector < int > bb) {
for(int i = 0; i < r.size(); i++)a[++n] = mp(r[i], 1);
for(int i = 0; i < bb.size(); i++)a[++n] = mp(bb[i], 0);
sort(a + 1, a + n + 1);
for(int i = 1; i <= n; i++)
pre[i] = pre[i - 1] + a[i].st;
for(int i = 1; i <= n; i++){
int j = i + 1;
while(j <= n and a[j].nd == a[j - 1].nd)
j++;
b[++m] = mp(i, j - 1);
// cout << i << " " << j - 1 << endl;
i = j - 1;
}
if(m == 1)return 0;
for(ll i = 1; i <= b[1].nd; i++)
dp[i] = i*a[b[2].st].st - pre[i];
for(ll j = 2; j <= m; j++){
l1 = b[j - 1].st;
r1 = b[j - 1].nd;
l2 = b[j].st;
r2 = b[j].nd;
for(ll i = l2; i <= r2; i++){
dp[i] = inf;
if(i - l2 + 1 <= r1 - l1 + 1){
dp[i] = dp[r1 - (i - l2 + 1)] + (pre[i] - pre[l2 - 1]) - (pre[r1] - pre[r1 - (i - l2 + 1)]);
}
if(j + 1 <= m)
dp[i] = min(dp[i], dp[i - 1] + (a[b[j + 1].st].st - a[i].st));
dp[i] = min(dp[i], dp[i - 1] + (a[i].st - a[b[j - 1].nd].st));
// cout << i << " " << dp[i] << endl;
}
}
return dp[n];
}
// int main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
// 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]));
// ll res = min_total_length(r, b);
// printf("%lld\n", res);
// return 0;
// }
