#include "wiring.h"
#include <bits/stdc++.h>
using ll = long long;
using std::vector;
using std::array;
using std::pair;
using std::tuple;
template <class T>
constexpr T infty = std::numeric_limits<T>::max() / 2;
ll min_total_length(vector<int> A, vector<int> B) {
int ai = 0, bi = 0;
vector<int> left;
vector<ll> dp;
while (ai < (int)A.size() or bi < (int)B.size()) {
if (ai == (int)A.size() or (bi < (int)B.size() and A[ai] > B[bi])) {
std::swap(A, B);
std::swap(ai, bi);
}
vector<int> right;
while (ai < (int)A.size() and (bi == (int)B.size() or A[ai] < B[bi])) {
right.push_back(A[ai]);
ai += 1;
}
const int lsz = (int)left.size();
const int rsz = (int)right.size();
if (lsz == 0) {
left = std::move(right);
dp.resize(rsz + 1, infty<ll>);
dp[rsz] = 0;
continue;
}
vector<ll> lsum(lsz + 1);
for (int i = 0; i < lsz; ++i) {
lsum[i + 1] = lsum[i] + (left[lsz - 1] - left[lsz - i - 1]);
}
vector<ll> rsum(rsz + 1);
for (int i = 0; i < rsz; ++i) {
rsum[i + 1] = rsum[i] + (right[i] - right[0]);
}
const ll between = right[0] - left[lsz - 1];
vector<ll> pre1(lsz + 1), pre2(lsz + 1);
for (int l = 1; l <= lsz; ++l) {
pre1[l] = dp[l] + lsum[l];
pre2[l] = dp[l] + lsum[l] + between * l;
}
for (int l = 2; l <= lsz; ++l) {
pre1[l] = std::min(pre1[l], pre1[l - 1]);
}
for (int l = lsz - 1; l >= 1; --l) {
pre2[l] = std::min(pre2[l], pre2[l + 1]);
}
vector<ll> next(rsz + 1);
next[0] = dp[0];
for (int r = 1; r <= rsz; ++r) {
// 1 <= l <= r : dp[l] + lsum[l] + rsum[r] + between * r
// r <= l : dp[l] + lsum[l] + rsum[r] + between * l
if (r <= lsz) {
next[r] = std::min(pre1[r] + rsum[r] + between * r, pre2[r] + rsum[r]);
} else {
next[r] = pre1[lsz] + rsum[r] + between * r;
}
}
left = std::move(right);
dp.resize(rsz + 1);
for (int i = 0; i <= rsz; ++i) {
dp[rsz - i] = next[i];
}
}
return dp[0];
}
