Покос
Младшие кузены Бесси, Элла и Белла, посетили ферму. К сожалению, с момента своего прибытия они не принесли ничего, кроме вреда.
В своей последней затее они решили скосить как можно больше травы. Лучшие пастбища фермы имеют форму большого квадрата t × t. Нижний левый угол имеет координаты (0, 0), а верхний правый угол - (t, t). Таким образом, квадрат содержит (t + 1) * (t + 1) точек решетки (точек с целочисленными координатами).
Элла и Белла планируют начать с точки (0, 0) и двигаться с единичной скоростью до (t, t), удерживая концы очень острой и очень длинной проволоки. Трава в любой области, по которой будет пронесен этот провод, будет обрезана. Элла и Белла могут идти разными путями, но каждый путь состоит только из шагов вверх и вправо, совершая переходы по точкам решетки.
Бесси очень обеспокоена тем, что будет срезано слишком много травы, поэтому она изобретает хитрый план, чтобы ограничить пути, по которым идут Элла и Белла. По лугам разбросано n вкусных цветов, каждый из которых расположен в отдельной точке решетки. Бесси выбирает набор цветов S, который потребуются Элле и Белле для посещения (так что путь Эллы должен посетить все цветы из S, как и путь Беллы). Чтобы добавить как можно больше путевых точек к этим путям, Бесси выберет S как можно большим среди подмножеств цветов, которые может посетить корова, движущаяся вверх и вправо от (0, 0) до (t, t).
Элла и Белла будут стараться срезать как можно больше травы, с учетом ограничения посещения цветов из S. Помогите Бесси выбрать S так, чтобы срезанной травы было как можно меньше.
Входные данные
Первая строка содержит числа n (1 ≤ n ≤ 2 * 10^5) и t (1 ≤ t ≤ 10^6). Каждая из следующих n строк содержит целочисленные координаты (x[i], y[i]) цветка. Гарантируется, что 1 ≤ x[i], y[i] ≤ t − 1 для всех i, и никакие два цветка не лежат на одной горизонтальной или вертикальной прямой.
Выходные данные
Выведите одно целое число - минимально возможное количество скошенной травы.
Пример
В этом примере для Бесси оптимально собрать цветы в точках (10, 3) и (13, 11). В худшем случае Элла и Белла вырежут три прямоугольника травы общей площадью 117.