#include "wiring.h"
#include <string.h>
using namespace std;
typedef vector<int> vi;
const int N = 100000, M = 100000;
const int SMALL = 200;
int abs_(int x) { return x > 0 ? x : -x; }
long long min(long long a, long long b) { return a < b ? a : b; }
long long dp[M + N + 1];
long long min_total_length(vi aa, vi bb) {
int n = aa.size(), m = bb.size(), i, j, k, o, x;
if (n <= SMALL && m <= SMALL) {
i = 0, j = 0, o = n, x = min(aa[0], bb[0]);
while (i < n || j < m)
if (i < n && (j == m || aa[i] < bb[j])) {
for (k = 0; k <= n + m; k++)
dp[k] += (long long) (aa[i] - x) * abs_(k - o);
x = aa[i];
i++, o--;
for (k = 1; k <= n + m; k++)
dp[k] = min(dp[k], dp[k - 1]);
} else {
for (k = 0; k <= n + m; k++)
dp[k] += (long long) (bb[j] - x) * abs_(k - o);
x = bb[j];
j++, o++;
for (k = n + m - 1; k >= 0; k--)
dp[k] = min(dp[k], dp[k + 1]);
}
return dp[o];
} else {
long long ans = 0;
for (i = 0; i < n; i++)
ans -= aa[i];
for (j = 0; j < m; j++)
ans += bb[j];
if (n > m)
ans += (long long) bb[0] * (n - m);
else
ans -= (long long) aa[n - 1] * (m - n);
return ans;
}
}
