#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// Subtask 1) O(N^3) = +7 points <-- this solution
// Subtask 2) Trivial = +13 points
ll findSmall(vector<int> r, vector<int> b, int isRed, int index, int maxIndex){
if(!isRed) swap(r, b);
ll minDist = 1e9;
for(int i = 0; i < b.size(); i++){
int bVal = b[i];
if(i > maxIndex) return minDist;
minDist = min(
minDist,
ll(abs(r[index] - bVal))
);
}
return minDist;
}
ll solveN3(vector<int>& r, vector<int>& b){
ll MAX = 1e18;
int M = b.size(); int N = r.size();
vector<vector<ll>> dp(M, vector<ll>(N, MAX));
dp[0][0] = abs(b[0] - r[0]);
for(int m = 0; m < M; m++){
for(int n = 0; n < N; n++){
if(m == 0 && n == 0) continue;
if(n == 0){
dp[m][n] = dp[m - 1][n] + abs(b[m] - r[0]);
continue;
}
if(m == 0){
dp[m][n] = dp[m][n - 1] + abs(b[m] - r[n]);
continue;
}
dp[m][n] = min({
dp[m][n - 1] + findSmall(r, b, true, n, m),
dp[m - 1][n - 1] + abs(b[m] - r[n]),
dp[m - 1][n] + findSmall(r, b, false, m, n)
});
}
}
return dp[M - 1][N - 1];
}
long long min_total_length(vector<int> r, vector<int> b) {
// return solveN3(r, b);
int N = r.size(); int M = b.size();
int meetingPoint = b[0];
ll distance = 0;
for(int i = 0; i < N; i++){
distance += abs(r[i] - meetingPoint);
}
for(int i = 0; i < M; i++){
distance += abs(b[i] - meetingPoint);
}
// Handle cases where: N != M
if(M > N){
distance += abs(meetingPoint - r[N - 1]);
}
return distance;
}
// #include "grader.cpp"
