#include "wiring.h"
#include <iostream>
#define MAX 1000000000000
using namespace std;
typedef long long ll;
ll sub1Dp[210][210]; // sub1Dp[i][j]: minCost when connecting r[0~i], b[0~j]
ll abs(ll x) {
return x>=0 ? x:-x;
}
bool isSub1(int rSize, int bSize) {
return rSize<=200 && bSize<=200;
}
ll sub1(vector<int> &r, vector<int> &b) {
int n = r.size(), m = b.size();
sub1Dp[0][0] = abs(r[0] - b[0]);
for(int j=1; j<m; j++) {
sub1Dp[0][j] = sub1Dp[0][j-1] + abs(r[0] - b[j]);
}
for(int i=1; i<n; i++) {
sub1Dp[i][0] = sub1Dp[i-1][0] + abs(r[i] - b[0]);
for(int j=1; j<m; j++) {
// r[i], b[j] should be connected
ll connectingCost = abs(r[i] - b[j]);
// case 1: r[i], b[j] are seperated to the rest
ll t = sub1Dp[i-1][j-1]; // t is the restCost
// case 2: r[i] is connected to the rest
// in this case, b[j] is seperated to the rest
t = min(t, sub1Dp[i][j-1]);
// case 3: b[j] is connected to the rest
// in this case, r[i] is seperated to the rest
t = min(t, sub1Dp[i-1][j]);
sub1Dp[i][j] = t + connectingCost;
}
}
return sub1Dp[n-1][m-1];
}
bool isSub2(vector<int> &r, vector<int> &b) {
return r.back() < b[0];
}
ll sub2(vector<int> &r, vector<int> &b) {
int n = r.size(), m = b.size();
ll rSum = 0;
for(int i=0; i<n; i++) {
rSum += r[n-1] - r[i];
}
ll bSum = 0;
for(int j=0; j<m; j++) {
bSum += b[j] - b[0];
}
ll connectingCost = (b[0] - r[n-1]) * max(n, m);
return rSum + bSum + connectingCost;
}
ll min_total_length(vector<int> r, vector<int> b) {
int n = r.size(), m = b.size();
if(isSub1(n, m)) {
return sub1(r, b);
}
else if(isSub2(r, b)) {
return sub2(r, b);
}
else return 0;
}
