#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
std::vector<int> R, B;
vector<pair<int, bool>> C; // false -> red, true -> blue
std::vector<int> C2O; // next different color index
vector<vector<long long>> memoiazion;
int A, N, K; // N -> red, K -> blue
long long dp(int a, int nk, int mk){
if (a == N + K){
return 0;
}
int combined = nk - mk + K;
if (memoiazion[a][combined] != -1){
return memoiazion[a][combined];
}
if (C[a].second && mk){
memoiazion[a][combined] = dp(a + 1, nk, mk - 1);
return memoiazion[a][combined];
}
if (!C[a].second && nk){
memoiazion[a][combined] = dp(a + 1, nk - 1, mk);
return memoiazion[a][combined];
}
if (C[a].second){
if (C2O[a] == 0)
memoiazion[a][combined] = dp(a + 1, nk, mk) + R[C2O[a]] - C[a].first;
else if (C2O[a] == N)
memoiazion[a][combined] = dp(a + 1, nk, mk) + C[a].first - R[C2O[a] - 1];
else
memoiazion[a][combined] = dp(a + 1, nk, mk) + min(R[C2O[a]] - C[a].first, C[a].first - R[C2O[a] - 1]);
if (C2O[a] + nk < N){
memoiazion[a][combined] = min(memoiazion[a][combined], dp(a + 1, nk + 1, mk) + R[C2O[a] + nk] - C[a].first);
}
return memoiazion[a][combined];
}
if (C2O[a] == 0)
memoiazion[a][combined] = dp(a + 1, nk, mk) + B[C2O[a]] - C[a].first;
else if (C2O[a] == K)
memoiazion[a][combined] = dp(a + 1, nk, mk) + C[a].first - B[C2O[a] - 1];
else
memoiazion[a][combined] = dp(a + 1, nk, mk) + min(B[C2O[a]] - C[a].first, C[a].first - B[C2O[a] - 1]);
if (C2O[a] + mk < K){
memoiazion[a][combined] = min(memoiazion[a][combined], dp(a + 1, nk, mk + 1) + B[C2O[a] + mk] - C[a].first);
}
return memoiazion[a][combined];
}
long long min_total_length(std::vector<int> r, std::vector<int> b) {
N = r.size();
K = b.size();
R.resize(N);
B.resize(K);
C2O.resize(N + K);
C.resize(N + K);
for (int i = 0; i < N; i++){
R[i] = r[i];
}
for (int i = 0; i < K; i++){
B[i] = b[i];
}
int j = 0;
for (int i = 0; i < K + N; i++){
if (j == N){
C[i].first = B[i - j];
C[i].second = true;
C2O[i] = j;
}else if (i - j == K){
C[i].first = R[j];
C[i].second = false;
C2O[i] = i - j;
j++;
}else if (B[i - j] < R[j]){
C[i].first = B[i - j];
C[i].second = true;
C2O[i] = j;
}else{
C[i].first = R[j];
C[i].second = false;
C2O[i] = i - j;
j++;
}
}
memoiazion.resize(N + K, vector<long long>(N + K + 1, -1));
return dp(0, 0, 0);
}
