#include "breakthru.h"
#include<bits/stdc++.h>
using namespace std;
const int N=20005,Mx=1e9;
int n,m,p[N],cp,a[N],b[N];
typedef long long ll;
const ll inf=1e18;
typedef pair<ll,ll> pll;
vector<pll>C;
pll tr[N<<2],tg[N<<2];
ll ad[N<<2];
#define L k<<1
#define R k<<1|1
void build(){
	for(int i=1;i<4*m;++i)tg[i]={inf,inf},ad[i]=0,tr[i]={0,0};
}
void pushtg(int k,ll v,pll w){
	ad[k]+=v;
	tg[k].first+=v;
	tr[k].first+=v;
	tg[k]=min(tg[k],w);
	tr[k]=min(tr[k],w);
}
void pushdown(int k){
	pushtg(L,ad[k],tg[k]);
	pushtg(R,ad[k],tg[k]);
	ad[k]=0,tg[k]={inf,inf};
}
void Add(int k,int l,int r,int x,int y,ll v){
	if(y<l||x>r)return;
	if(x<=l&&r<=y)return pushtg(k,v,{inf,inf});
	pushdown(k);
	int mid=l+r>>1;
	Add(L,l,mid,x,y,v),Add(R,mid+1,r,x,y,v);
	tr[k]=min(tr[L],tr[R]);
}
ll cost(pll v,int A,int B){
	return v.first*A+v.second*B;
}
pll solve(int A,int B){
	build();
	for(int i=0;i<n;++i){
		Add(1,1,m,a[i],b[i],B);
		pll v=tr[1];
		++v.second,v.first+=A;
		pushtg(1,0,v);
	}
	auto [v,cA]=tr[1];
	return {cA,(v-A*cA)/B};
}
void work(pll A,pll B){
	int vA=A.second-B.second,vB=B.first-A.first;
	pll D=solve(vA,vB);
	if(cost(D,vA,vB)==cost(A,vA,vB))C.push_back(B);
	else work(A,D),work(D,B);
}
void init(int _n,int _m,vector<int>Y1,vector<int>Y2){
	n=_n,m=_m;
	p[++cp]=0,p[++cp]=m;
	for(int i=0;i<n;++i)p[++cp]=Y1[i],p[++cp]=Y2[i]+1;
	sort(p+1,p+cp+1);
	m=unique(p+1,p+cp+1)-p-1;
	for(int i=0;i<n;++i){
		a[i]=lower_bound(p+1,p+m+1,Y1[i])-p;
		b[i]=upper_bound(p+1,p+m+1,Y2[i])-p-1;
	}
	--m;
	pll A=solve(Mx,1),B=solve(1,Mx);
	C.push_back(A);
	if(A!=B)work(A,B);assert(C.size()<100);
}
ll minimize(int _A,int _B){
	int A=_A,B=_B;
	int l=0,r=C.size()-1;
	while(l<r){
		int mid=l+r>>1;
		if(cost(C[mid],A,B)<cost(C[mid+1],A,B))r=mid;
		else l=mid+1;
	}
	return cost(C[l],A,B);
}