#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#include "wiring.h"
#if defined(LOCAL) && __has_include("../../debug.h")
#include "../../debug.h"
#elif defined(LOCAL) && __has_include("../debug.h")
#include "../debug.h"
#elif defined(LOCAL) && __has_include("debug.h")
#include "debug.h"
#else
#define debug(...) ((void)0)
#endif
const ll INF = 1e16;
ll min_total_length(vector<int> r, vector<int> b) {
vector<pair<int, int>> all;
int i = 0, j = 0;
while(i < r.size() || j < b.size()) {
if(i < r.size() && (j == b.size() || r[i] < b[j]))
all.push_back({r[i++], 0});
else
all.push_back({b[j++], 1});
}
vector<vector<int>> blocks;
vector<int> curr = {all[0].first};
for(int k = 1; k < all.size(); ++k) {
if(all[k].second == all[k - 1].second)
curr.push_back(all[k].first);
else {
blocks.push_back(curr);
curr = {all[k].first};
}
}
blocks.push_back(curr);
int m = ssize(blocks);
vector<ll> dp(blocks[0].size() + 1, INF);
dp[0] = 0;
for(i = 0; i < m - 1; i++) {
vector<int> &b1 = blocks[i];
vector<int> &b2 = blocks[i + 1];
int n1 = b1.size();
int n2 = b2.size();
ll dist = (ll)b2[0] - b1[n1 - 1];
vector<ll> d1(n1 + 1, 0), d2(n2 + 1, 0);
for(j = 0; j < n1; ++j) d1[j + 1] = d1[j] + (ll)(b2[0] - b1[n1 - j - 1]);
for(j = 0; j < n2; ++j) d2[j + 1] = d2[j] + (ll)(b2[j] - b1[n1 - 1]);
vector<ll> next_dp(n2 + 1, INF);
vector<ll> prefMin(n1 + 1, INF);
for(int k = 0; k <= n1; ++k) {
if(dp[n1 - k] != INF) prefMin[k] = dp[n1 - k] + d1[k];
}
for(int k = n1 - 1; k >= 0; --k) prefMin[k] = min(prefMin[k], prefMin[k + 1]);
vector<ll> prefMin2(n1 + 1, INF);
for(int k = 0; k <= n1; ++k) {
if(dp[n1 - k] != INF) prefMin2[k] = dp[n1 - k] + d1[k] - (ll)k * dist;
}
for(int k = 1; k <= n1; ++k) prefMin2[k] = min(prefMin2[k], prefMin2[k - 1]);
next_dp[0] = dp[n1];
for(j = 1; j <= n2; j++) {
// k >= j
int ks = j;
if(ks <= n1 && prefMin[ks] != INF) {
next_dp[j] = min(next_dp[j], prefMin[ks] + d2[j] - (ll)j * dist);
}
// k < j
int ke = min(j - 1, n1);
if(prefMin2[ke] != INF) {
next_dp[j] = min(next_dp[j], prefMin2[ke] + d2[j]);
}
next_dp[j] = min(next_dp[j], next_dp[j - 1] + (ll)(b2[j - 1] - b1[n1 - 1]));
}
dp = next_dp;
debug(dp);
}
return dp.back();
}
// int main() {
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// int n, m;
// cin >> n >> m;
// vector<int> a(n), b(m);
// for(int &i : a) cin >> i;
// for(int &i : b) cin >> i;
// cout << min_total_length(a, b) << "\n";
// return 0;
// }
