#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;
#define INIT ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<ll, ll>
#define count_bits __builtin_popcount
//#define int ll
ll n, m, g;
vector<pii> arr;
vector<ll> c[200010];
vector<ll> dp[200010];
vector<ll> mn1[200010], mn2[200010];
vector<ll> s[200010];
ll sz[200010];
void build_mn1(ll i){
for(ll j=1; j<=sz[i]; j++){
mn1[i][j]=dp[i][sz[i]-j ]-(s[i][sz[i] ]-s[i][sz[i]-j])+c[i][sz[i] ]*j;
if(j>1){
mn1[i][j]=min(mn1[i][j], mn1[i][j-1]);
}
}
}
void build_mn2(ll i){
if(i<g){
for(ll j=sz[i]; j>=1; j--){
mn2[i][j]=dp[i][sz[i]-j ]+j*(c[i+1][1])-(s[i][sz[i] ]-s[i][sz[i]-j] );
if(j<sz[i]){
mn2[i][j]=min(mn2[i][j], mn2[i][j+1]);
}
}
}
}
void precalc(ll i){
build_mn1(i);
build_mn2(i);
}
void build_dp(){
for(ll i=1; i<=g; i++){
for(ll j=1; j<=sz[i]; j++){
s[i][j]=s[i][j-1]+c[i][j];
}
}
for(ll j=1; j<=sz[2]; j++){
if(j<=sz[1] ){
dp[2][j]=s[2][j]-(s[1][sz[1]]-s[1][sz[1]-j]);
}
else{
dp[2][j]=s[2][j]-( s[1][sz[1] ]+(j-sz[1])*(c[1][sz[1] ]) );
}
}
//cout<<"ok"<<flush;
precalc(2);
//cout<<"ok"<<flush;
for(ll i=3; i<=g; i++){
dp[i][0]=dp[i-1][sz[i-1] ];
for(ll j=1; j<=sz[i]; j++){
if(j>sz[i-1]){
dp[i][j]=s[i][j]-( (s[i-1][sz[i-1] ]+(j-sz[i-1])*c[i-1][sz[i-1] ]) )+dp[i-2][sz[i-2] ];
}
else{
dp[i][j]=min( mn1[i-1][j]+s[i][j]-j*(c[i-1][sz[i-1] ]), mn2[i-1][j]+s[i][j]-j*c[i][1] );
}
}
precalc(i);
}
}
long long min_total_length(std::vector<int> r, std::vector<int> b) {
n=r.size(), m=b.size();
for(ll i=0, j=0; (i<n) ||(j<m); ){
if(i==n){
arr.pb({b[j], 0});
j++;
}
else{
if(j==m){
arr.pb({r[i], 1});
i++;
}
else{
if(r[i]<=b[j]){
arr.pb({r[i], 1});
i++;
}
else{
arr.pb({b[j], 0});
j++;
}
}
}
}
g=1;
//g++;
c[g].pb(0);
c[g].pb(arr[0].ft);
for(ll i=1, ac=arr[0].sc; i<(m+n); i++){
if(ac!=arr[i].sc){
g++;
c[g].pb(0);
c[g].pb(arr[i].ft);
ac=arr[i].sc;
}
else{
c[g].pb(arr[i].ft);
}
}
//dp[1][1]
//cout<<"ok"<<flush;
for(ll i=1; i<=g; i++){
dp[i].assign(((ll)c[i].size()), 0ll);
mn1[i].assign(((ll)c[i].size()), 0ll);
mn2[i].assign(((ll)c[i].size()), 0ll);
s[i].assign(((ll)c[i].size()), 0ll);
sz[i]=c[i].size()-1;
}
//cout<<"ok"<<flush;
build_dp();
return dp[g][sz[g] ];
}
