#include "breakthru.h"
#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const int N = 30005, L = (1<<16);
const ll inf = 1e18;
 
int yl, n, s[N], e[N];
 
vector<int> cpr;
vector<pii> cand;
 
struct Node {
	pll v, l2;
	ll l1;
};
 
struct segtree {
	Node v[2*L];
	void init () {
		for(int i=0;i<2*L;i++) {
			v[i].v = {0, 0};
			v[i].l1 = 0;
			v[i].l2 = {inf, inf};
		}
	}
	void lazydown (int P) {
		for(int i=2*P;i<=2*P+1;i++) {
			v[i].v.X += v[P].l1;
			v[i].l1 += v[P].l1;
			v[i].l2.X += v[P].l1;
			if(v[i].v > v[P].l2) v[i].v = v[P].l2;
			if(v[i].l2 > v[P].l2) v[i].l2 = v[P].l2;
		}
		v[P].l1 = 0;
		v[P].l2 = {inf, inf};
	}
	void add (int S, int E, int X, int SS = 0, int SE = L-1, int P = 1) {
		if(S <= SS && SE <= E) {
			v[P].v.X += X;
			v[P].l1 += X;
			v[P].l2.X += X;
			return;
		}
		if(E < SS || SE < S) return;
		lazydown(P);
		int M = (SS+SE)/2;
		add(S, E, X, SS, M, 2*P);
		add(S, E, X, M+1, SE, 2*P+1);
		v[P].v = min(v[2*P].v, v[2*P+1].v);
	}
	void cut (int S, int E, pll X, int SS = 0, int SE = L-1, int P = 1) {
		if(S <= SS && SE <= E) {
			v[P].v = min(v[P].v, X);
			v[P].l2 = min(v[P].l2, X);
			return;
		}
		if(E < SS || SE < S) return;
		lazydown(P);
		int M = (SS+SE)/2;
		cut(S, E, X, SS, M, 2*P);
		cut(S, E, X, M+1, SE, 2*P+1);
		v[P].v = min(v[2*P].v, v[2*P+1].v);
	}
	pll get (int S, int E, int SS = 0, int SE = L-1, int P = 1) {
		if(S <= SS && SE <= E) return v[P].v;
		if(E < SS || SE < S) return {inf, inf};
		lazydown(P);
		int M = (SS+SE)/2;
		return min(get(S, E, SS, M, 2*P), get(S, E, M+1, SE, 2*P+1));
	}
} seg;
 
ll cost (pii T, int A, int B) {
	return 1ll*T.X*A + 1ll*T.Y*B;
}
 
pii solve (int A, int B) {
	seg.init();
	for(int i=0;i<n;i++) {
		seg.add(s[i], e[i], B);
		pll T = seg.get(0, (int)cpr.size()-2);
		seg.cut(s[i], e[i], {T.X + A, T.Y + 1});
	}
	pll R = seg.get(0, (int)cpr.size()-2);
	return {R.Y, (R.X - R.Y * A) / B};
}
 
void conquer (pii A, pii B) {
	int VA = A.Y - B.Y, VB = B.X - A.X;
	pii T = solve(VA, VB);
	if(cost(T, VA, VB) == cost(A, VA, VB)) {
		cand.push_back(B);
	}
	else {
		conquer(A, T);
		conquer(T, B);
	}
}
 
void init (int _n, int _m, std::vector<int> _ys, std::vector<int> _ye) {
	yl = _m;
	n = _n;
	cpr.push_back(0);
	cpr.push_back(yl);
	for(int i=0;i<n;i++) {
		s[i] = _ys[i];
		e[i] = _ye[i];
		cpr.push_back(_ys[i]);
		cpr.push_back(_ye[i]+1);
	}
	sort(cpr.begin(), cpr.end());
	cpr.erase(unique(cpr.begin(), cpr.end()), cpr.end());
	for(int i=0;i<n;i++) {
		s[i] = lower_bound(cpr.begin(), cpr.end(), s[i]) - cpr.begin();
		e[i] = lower_bound(cpr.begin(), cpr.end(), e[i]+1) - cpr.begin() - 1;
	}
	pii A = solve(N, 1), B = solve(1, N);
	cand.push_back(A);
	if(A != B) conquer(A, B);
}
 
ll minimize (int _a, int _b) {
	int S = 0, E = (int)cand.size()-1;
	while(S<E) {
		int M = (S+E)/2;
		cost(cand[M], _a, _b) < cost(cand[M+1], _a, _b) ? E = M : S = M+1;
	}
	return cost(cand[S], _a, _b);
}