#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
std::vector<int> C2N; // current color index
vector<int> B2C, R2C;
vector<long long> Cclose;
long long *prefixCclose;
vector<long long> memoiazion;
int A, N, K; // N -> red, K -> blue
long long dp(int a){
if (a >= N + K){
return 0;
}
if (memoiazion[a] != -1){
return memoiazion[a];
}
if (C[a].second){
memoiazion[a] = prefixCclose[N + K - 1] - prefixCclose[a - 1];
long long int add = 0;
for (int i = C2O[a], j = C2N[a]; i < N && j < K; i++, j++){
add += -Cclose[B2C[j]] - Cclose[R2C[i]] + abs(C[R2C[i]].first - C[B2C[j]].first);
if (memoiazion[a] < dp(max(R2C[i], B2C[j]) + 1) + prefixCclose[max(R2C[i], B2C[j])] - prefixCclose[a - 1] + add)
break;
memoiazion[a] = dp(max(R2C[i], B2C[j]) + 1) + prefixCclose[max(R2C[i], B2C[j])] - prefixCclose[a - 1] + add;
}
return memoiazion[a];
}
memoiazion[a] = prefixCclose[N + K - 1] - prefixCclose[a - 1];
long long int add = 0;
for (int i = C2O[a], j = C2N[a]; i < K && j < N; i++, j++){
add += -Cclose[R2C[j]] - Cclose[B2C[i]] + abs(C[B2C[i]].first - C[R2C[j]].first);
if (memoiazion[a] < dp(max(B2C[i], R2C[j]) + 1) + prefixCclose[max(B2C[i], R2C[j])] - prefixCclose[a - 1] + add)
break;
memoiazion[a] = dp(max(B2C[i], R2C[j]) + 1) + prefixCclose[max(B2C[i], R2C[j])] - prefixCclose[a - 1] + add;
}
return memoiazion[a];
}
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);
R2C.resize(N);
B2C.resize(K);
C2O.resize(N + K);
C2N.resize(N + K);
C.resize(N + K);
Cclose.resize(N + K);
prefixCclose = new long long[N + K + 1];
prefixCclose[0] = 0;
prefixCclose++; // index -1 = 0
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];
B2C[i - j] = i;
C[i].second = true;
C2O[i] = j;
C2N[i] = i - j;
}else if (i - j == K){
C[i].first = R[j];
R2C[j] = i;
C[i].second = false;
C2O[i] = i - j;
C2N[i] = j;
j++;
}else if (B[i - j] < R[j]){
C[i].first = B[i - j];
B2C[i - j] = i;
C[i].second = true;
C2O[i] = j;
C2N[i] = i - j;
}else{
C[i].first = R[j];
R2C[j] = i;
C[i].second = false;
C2O[i] = i - j;
C2N[i] = j;
j++;
}
}
for (int i = 0; i < N + K; i++){
if (C[i].second){
if (C2O[i] == 0)
Cclose[i] = R[C2O[i]] - C[i].first;
else if (C2O[i] == N)
Cclose[i] = C[i].first - R[C2O[i] - 1];
else
Cclose[i] = min(R[C2O[i]] - C[i].first, C[i].first - R[C2O[i] - 1]);
}else{
if (C2O[i] == 0)
Cclose[i] = B[C2O[i]] - C[i].first;
else if (C2O[i] == K)
Cclose[i] = C[i].first - B[C2O[i] - 1];
else
Cclose[i] = min(B[C2O[i]] - C[i].first, C[i].first - B[C2O[i] - 1]);
}
}
for (int i = 0; i < N + K; i++){
prefixCclose[i] = prefixCclose[i - 1] + Cclose[i];
}
memoiazion.resize(N + K, -1);
return dp(0);
}
