#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
pair<vector<long long>, vector<long long>> utils(vector<long long> &dp, vector<int> &block, long long F) {
int N0 = (int)block.size(), L = block.back();
vector<long long> jl(N0 + 1), jg(N0 + 1);
vector<long long> best(N0 + 1, inf); best[N0] = dp[N0];
for (int j = N0 - 1; j >= 0; j--) best[j] = min(best[j + 1], dp[j]);
long long sf = 0;
for (int j = N0; j >= 0; j--) {
jg[j] = best[j] - 1LL*j*L - sf;
jl[j] = best[j] - 1LL*j*F - sf;
if (j) sf += block[j - 1];
}
jl[N0] = jg[N0] = inf;
for (int j = 1; j <= N0; j++) jl[j] = min(jl[j], jl[j - 1]);
for (int j = N0 - 1; j >= 0; j--) jg[j] = min(jg[j], jg[j + 1]);
return {jg, jl};
}
long long min_total_length(vector<int> r, vector<int> b) {
vector<pair<int, int>> pts;
for (auto &x : r) pts.push_back({x, 0});
for (auto &x : b) pts.push_back({x, 1});
sort(pts.begin(), pts.end());
vector<vector<int>> blocks; blocks.push_back({pts[0].first});
for (int i = 1; i < (int)pts.size(); i++) {
if (pts[i].second != pts[i - 1].second) {
blocks.push_back({pts[i].first});
continue;
}
blocks.back().push_back(pts[i].first);
}
vector<long long> dpprev, jg, jl, dpcur;
dpprev.assign(blocks[0].size()+1, inf);
dpprev[0] = 0;
for (int b = 1; b < (int)blocks.size(); b++) {
auto block = blocks[b];
int N1 = (int)block.size(), N0 = (int)blocks[b - 1].size(), L = blocks[b - 1].back(), F = block[0];
dpcur.assign(N1+1, inf); dpcur[0] = dpprev.back();
pair<vector<long long>, vector<long long>> ut = utils(dpprev, blocks[b - 1], block[0]);
jg = ut.first; jl = ut.second;
long long psum = 0;
for (int i = 1; i <= N1; i++) {
int ct = N0 - i; psum += block[i-1];
dpcur[i] = min(dpcur[i], psum - (long long)i*(long long)L + (long long)N0*(long long)L + jg[max(0, ct)]);
if (ct >= 0) dpcur[i] = min(dpcur[i], psum - 1LL*i*F + 1LL*N0*F + jl[ct]);
}
dpprev = dpcur;
}
return dpprev.back();
}
