#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=1000000007;
const ll mod2=998244353;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head
ll min_total_length(VI r,VI b) {
int n=SZ(r)+SZ(b);
vector<PII> a;
rep(i,0,SZ(r)) a.pb(mp(r[i],0));
rep(i,0,SZ(b)) a.pb(mp(b[i],1));
sort(all(a));
vector<PII> segs;
rep(i,0,n) {
int ptr=i;
while (ptr+1<n&&a[ptr+1].se==a[i].se) ptr++;
segs.pb(mp(i,ptr));
i=ptr;
}
int m=SZ(segs);
vector<vector<ll>> mn(m),mx(m),ps(m),ss(m);
vector<ll> dp(n,1e17);
rep(i,0,m) {
int l=segs[i].fi,r=segs[i].se;
int len=r-l+1;
mn[i].resize(len);
mx[i].resize(len);
ps[i].resize(len);
ss[i].resize(len);
rep(j,1,len) ps[i][j]=ps[i][j-1]+a[l+j].fi-a[l].fi;
per(j,0,len-1) ss[i][j]=ss[i][j+1]+a[r].fi-a[l+j].fi;
if (i!=0) {
rep(j,0,len) {
dp[l+j]=1e18;
dp[l+j]=min(dp[l+j],ps[i][j]+mn[i-1][max(0,SZ(mn[i-1])-j-1)]+(ll)(j+1)*(a[l].fi-a[l-1].fi));
if (j+1<SZ(mx[i-1])) dp[l+j]=min(dp[l+j],ps[i][j]+mx[i-1][SZ(mx[i-1])-j-2]);
// OMGG
dp[l+j]=min(dp[l+j],dp[segs[i-1].se]+ps[i][j]+(ll)(a[l].fi-a[l-1].fi)*(j+1));
}
/*rep(j,0,len) {
dp[j+l]=1e17;
rep(x,0,SZ(mx[i-1])) {
int L=segs[i-1].fi;
ll ft=(L+x>0?dp[L+x-1]:0LL)+ps[i][j]+ss[i-1][x]+(ll)(a[l].fi-a[l-1].fi)*max(j+1,SZ(mx[i-1])-x);
dp[l+j]=min(dp[l+j],ft);
}
}*/
}
if (i!=m-1) {
rep(j,0,len) {
mx[i][j]=(l+j>0?dp[l+j-1]:0LL)+ss[i][j]+(ll)(a[r+1].fi-a[r].fi)*(len-j);
if (j>0) mx[i][j]=min(mx[i][j],mx[i][j-1]);
}
per(j,0,len) {
mn[i][j]=ss[i][j]+(l+j>0?dp[l+j-1]:0LL);
if (j<len-1) mn[i][j]=min(mn[i][j],mn[i][j+1]);
}
}
}
return dp[n-1];
}
