#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAXN = 1e5+5;
const ll inf = 1e18;
ll dp[2][MAXN][7][2][2];
int nxt[MAXN][2];
int n;
int _abs(int v) {
return v < 0 ? -v : v;
}
ll hsh(int i, int j, bool lmatch, bool rmatch) {
return (ll) 4*i*n+4*j+2*lmatch+rmatch;
}
ll make_dp(int i, int j, bool lmatch, bool rmatch, vector<int> &r, vector<int> &b) {
int cur = i;
for (int _ = 0; _ < 3; _++) cur = nxt[cur][_&1];
if (cur <= j) return inf;
cur = j;
for (int _ = 1; _ < 4; _++) cur = nxt[cur][_&1];
if (cur <= i) return inf;
int cost = _abs(r[i]-b[j]);
if (i == r.size()-1 && j == b.size()-1) {
return cost;
}
ll dpval = (nxt[i][0] <= j) ? dp[0][i][j-nxt[i][0]][lmatch][rmatch] : dp[1][j][i-nxt[j][1]][lmatch][rmatch];
if (dpval != 0) return dpval;
ll ans = inf;
if (lmatch) ans = min(ans, make_dp(i+1, j, 0, rmatch, r, b));
ans = min(ans, make_dp(i+1, j, 0, 1, r, b)+cost);
if (rmatch) ans = min(ans, make_dp(i, j+1, lmatch, 0, r, b));;
ans = min(ans, make_dp(i, j+1, 1, 0, r, b)+cost);
if (nxt[i][0] <= j) dp[0][i][j-nxt[i][0]][lmatch][rmatch] = ans;
else dp[1][j][i-nxt[j][1]][lmatch][rmatch] = ans;
// cerr << i << ' ' << j << ' ' << lmatch << ' ' << rmatch << ' ' << ans << '\n';
return ans;
}
ll min_total_length(vector<int> r, vector<int> b) {
ll ans = 0;
for (int v: r) ans -= v;
for (int v: b) ans += v;
if (r.size() < b.size()) ans -= (ll)r.back()*(b.size()-r.size());
else ans += (ll)b.front()*(r.size()-b.size());
return ans;
// n = r.size()+b.size();
// int i = 0;
// nxt[r.size()][0] = b.size();
// nxt[b.size()][1] = r.size();
// for (int j = 0; j < b.size(); j++) {
// while (i < r.size() && r[i] < b[j]) i++;
// nxt[j][1] = i;
// }
// int j = 0;
// for (int i = 0; i < r.size(); i++) {
// while (j < b.size() && b[j] < r[i]) j++;
// nxt[i][0] = j;
// }
// ll ans = make_dp(0, 0, 0, 0, r, b);
// // assert(dp.size() < 7*n);
// return ans;
}
