/* https://codeforces.com/blog/entry/53550?#comment-375680 (majk) */
#include "wiring.h"
#include <string.h>
using namespace std;
typedef vector<int> vi;
const int N = 100000, M = 100000;
long long min(long long a, long long b) { return a < b ? a : b; }
int xx[N + M], cc[N + M];
long long dp[N + M + 1];
long long min_total_length(vi aa, vi bb) {
int n = aa.size(), m = bb.size(), p, h, i, j, k;
i = 0, j = 0, k = 0;
while (i < n || j < m)
if (i < n && (j == m || aa[i] < bb[j]))
xx[k] = aa[i++], cc[k] = 0, k++;
else
xx[k] = bb[j++], cc[k] = 1, k++;
n += m;
memset(dp, 0x3f, (n + 1) * sizeof *dp), dp[0] = 0;
for (p = 0, i = 0; i < n; p = i, i = j) {
long long x;
j = i + 1;
while (j < n && cc[j] == cc[i])
j++;
for (h = p; h <= i; h++)
dp[h] = min(dp[h], dp[h - 1] + xx[i] - xx[h - 1]);
x = 0;
for (h = i + 1; h <= j && i * 2 - h >= p; h++) {
x += xx[h - 1] - xx[i * 2 - h];
dp[h] = dp[i * 2 - h] + x;
}
if (i > 0)
for (h = i + 1; h <= j; h++)
dp[h] = min(dp[h], dp[h - 1] + xx[h - 1] - xx[i - 1]);
}
return dp[n];
}
