#include "wiring.h"
#include <iostream>
using namespace std;
long long int sum[1000005],col[1000005],ri[1000005],le[1000005],num[1000005],dp[1000005],n,m;
long long min_total_length(std::vector<int> r, std::vector<int> b) {
n=r.size();
m=b.size();
long long int pp=1,pa=0,pb=0;
while(pa<n && pb<m)
{
if(r[pa]<b[pb])
{
num[pp]=r[pa];
col[pp]=0;
pa++;
}
else
{
num[pp]=b[pb];
col[pp]=1;
pb++;
}
pp++;
}
while(pa<n)
{
num[pp]=r[pa];
col[pp]=0;
pa++;
pp++;
}
while(pb<m)
{
num[pp]=b[pb];
col[pp]=1;
pb++;
pp++;
}
col[0]=col[1];
col[n+m+1]=(col[n+m]+1)%2;
long long int st=1,cnt=0,cnt1=0,len=0;
for(int i=1;i<=n+m;i++)
{
if(col[i]!=col[i-1])
{
//cout<<" "<<i<<endl;
sum[st]=num[st];
for(int j=st+1;col[st]==col[j];j++)
{
sum[j]=sum[j-1]+num[j];
//cout<<sum[j]<<" ";
}
//cout<<endl;
for(int j=i-1;j>=st;j--)
{
ri[j]=num[i-1]*(i-j)-(sum[i-1]-sum[j-1])+min(dp[j],dp[j-1]);
if(j!=i-1)ri[j]=min(ri[j],ri[j+1]);
//cout<<ri[j]<<" ";
}
//cout<<endl;
for(int j=st;j<i;j++)
{
le[j]=num[i]*(i-j)-(sum[i-1]-sum[j-1])+min(dp[j],dp[j-1]);
if(j!=st)le[j]=min(le[j],le[j-1]);
//cout<<le[j]<<" ";
}
//cout<<endl;
sum[i-1]=0;
st=i,cnt1=cnt,cnt=1;
len=0;
}
else cnt++;
if(st==1)
{
dp[i]=99999999999999999;
continue;
}
len+=num[i]-num[st];
long long int tmp=len;
if(cnt>=cnt1)dp[i]=ri[st-cnt1]+cnt*(num[st]-num[st-1])+tmp;
else dp[i]=min(ri[st-cnt]+cnt*(num[st]-num[st-1]),le[st-cnt-1])+tmp;
//cout<<tmp<<" "<<num[i]<<" "<<col[i]<<" "<<dp[i]<<endl;
}
return dp[n+m];
}
