#pragma GCC optimize("O3")
#include "wiring.h"
#include <string.h>
using namespace std;
typedef vector<int> vi;
const int N = 100000, M = 100000, N_ = 1 << 18; // N_ = pow2(ceil(log2(N + M)))
const int X = 0x3f3f3f3f;
long long min(long long a, long long b) { return a < b ? a : b; }
int sz[N_ * 2]; long long mn[N_ * 2], mx[N_ * 2], sum[N_ * 2], lz2[N_]; char lz1[N_]; int h_, n_;
void put1(int i) {
mn[i] = mx[i] = sum[i] = 0;
if (i < n_)
lz2[i] = 0, lz1[i] = 1;
}
void put2(int i, long long x) {
mn[i] += x, mx[i] += x, sum[i] += sz[i] * x;
if (i < n_)
lz2[i] += x;
}
void pul(int i) {
if (!lz1[i] && !lz2[i]) {
mn[i] = mn[i << 1 | 0], mx[i] = mx[i << 1 | 1];
sum[i] = sum[i << 1 | 0] + sum[i << 1 | 1];
}
}
void pus(int i) {
int l = i << 1 | 0, r = i << 1 | 1;
if (lz1[i])
put1(l), put1(r), lz1[i] = 0;
if (lz2[i])
put2(l, lz2[i]), put2(r, lz2[i]), lz2[i] = 0;
}
void push(int i) {
int h;
for (h = h_; h > 0; h--)
pus(i >> h);
}
void pull(int i) {
while (i > 1)
pul(i >>= 1);
}
void build(int n, int m) {
int i;
h_ = 0;
while (1 << h_ < n + m)
h_++;
n_ = 1 << h_;
for (i = 0; i < n_; i++)
sz[n_ + i] = 1, mn[n_ + i] = mx[n_ + i] = sum[n_ + i] = i < n ? -X : X;
for (i = n_ - 1; i > 0; i--)
pul(i), sz[i] = sz[i << 1 | 0] + sz[i << 1 | 1];
}
void update(int l, int r, int x) {
int l_ = l += n_, r_ = r += n_;
if (l > r)
return;
push(l_), push(r_);
for ( ; l <= r; l >>= 1, r >>= 1) {
if ((l & 1) == 1)
put2(l++, x);
if ((r & 1) == 0)
put2(r--, x);
}
pull(l_), pull(r_);
}
long long ans;
void clear_l() {
int i = 1;
while (i < n_) {
pus(i);
if (mx[i << 1 | 0] < 0) {
ans += sum[i << 1 | 0], put1(i << 1 | 0);
i = i << 1 | 1;
} else
i = i << 1 | 0;
}
if (mx[i] < 0)
ans += sum[i], put1(i);
pull(i);
}
void clear_r() {
int i = 1;
while (i < n_) {
pus(i);
if (mn[i << 1 | 1] > 0) {
put1(i << 1 | 1);
i = i << 1 | 0;
} else
i = i << 1 | 1;
}
if (mn[i] > 0)
put1(i);
pull(i);
}
long long min_total_length(vi aa, vi bb) {
int n = aa.size(), m = bb.size(), i, j, o, x;
i = 0, j = 0, o = n, x = min(aa[0], bb[0]), ans = (long long) X * n;
build(n, m);
while (i < n || j < m)
if (i < n && (j == m || aa[i] < bb[j])) {
update(0, o - 1, x - aa[i]), update(o, n_ - 1, aa[i] - x);
ans += (long long) (aa[i] - x) * o;
x = aa[i++], o--;
clear_r();
} else {
update(0, o - 1, x - bb[j]), update(o, n_ - 1, bb[j] - x);
ans += (long long) (bb[j] - x) * o;
x = bb[j++], o++;
clear_l();
}
for (i = 1; i < n_; i++)
pus(i);
for (i = 0; i < o; i++)
ans += sum[n_ + i];
return ans;
}
