#include "breakthru.h"
#include<bits/stdc++.h>
#define LL long long
#define P pair<LL,LL>
#define fi first
#define se second
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int N=1e4+5,M=N<<3;const LL inf=1e17;
int n,m,V,q,l[N],r[N];LL lt[M];P a[M],lt1[M];
vector<P>T;
inline int mul(P A,P B,P C){return (B.fi-A.fi)*(C.se-A.se)-(C.fi-A.fi)*(B.se-A.se);}
inline void pushup(int wz){a[wz]=min(a[wz<<1],a[wz<<1|1]);}
inline void upd(int wz,LL x){a[wz].fi+=x,lt[wz]+=x,lt1[wz].fi+=x;}
inline void upd1(int wz,P x){a[wz]=min(a[wz],x);lt1[wz]=min(lt1[wz],x);}
inline void pushdown(int wz)
{
	LL &lt=::lt[wz];P &lt1=::lt1[wz];
	if(lt) upd(wz<<1,lt),upd(wz<<1|1,lt),lt=0;
	if(lt1.fi!=inf) upd1(wz<<1,lt1),upd1(wz<<1|1,lt1),lt1={inf,inf};
}
void updata(int l,int r,int wz,int L,int R,LL x)
{
	if(L<=l&&r<=R) return upd(wz,x);
	int mid=(l+r)>>1;pushdown(wz);
	if(L<=mid) updata(l,mid,wz<<1,L,R,x);
	if(mid<R) updata(mid+1,r,wz<<1|1,L,R,x);
	pushup(wz);
}
inline P sol(int A,int B)
{
	for(int i=1;i<=(m<<2);i++) lt[i]=0,a[i]=lt1[i]={0,0};
	for(int i=1;i<=n;i++)
	{
		updata(1,m,1,l[i],r[i],B);P t=a[1];
		upd1(1,{t.fi+A,t.se+1});
	}auto [u,v]=a[1];
	return {v,(u-v*A)/B};
}
void dfs(P A,P B)
{
	P C=sol(A.se-B.se,B.fi-A.fi);
	if(mul(A,B,C)<0) T.push_back(C),dfs(A,C),dfs(C,B);
}
inline LL MUL(P A,P B){return A.fi*B.fi+A.se*B.se;}
void init(int _n,int _m,vector<int>Y1,vector<int>Y2)
{
	n=_n,m=_m;basic_string<int>g;g+=0,g+=m;V=m;
	for(int i=1;i<=n;i++) l[i]=Y1[i-1],r[i]=Y2[i-1],g+=l[i],g+=r[i]+1;
	sort(g.begin(),g.end());g.erase(unique(g.begin(),g.end()),g.end());
	for(int i=1;i<=n;i++) l[i]=lower_bound(g.begin(),g.end(),l[i])-g.begin()+1,
	r[i]=upper_bound(g.begin(),g.end(),r[i])-g.begin();m=g.size()-1;
	P A=sol(V,1),B=sol(1,V);T.push_back(A),T.push_back(B);dfs(A,B);
	sort(T.begin(),T.end());
}
 LL minimize(int A,int B)
{
	P t={A,B};int l=0,r=T.size()-1,mid;
	while(l<r) mid=(l+r)>>1,(MUL(T[mid],t)<MUL(T[mid+1],t))?r=mid:l=mid+1;
	return MUL(T[l],t);
}