题目描述

题目译自 USACO 2019 February Contest, Platinum Problem 3. Mowing Mischief

Bessie 的表妹 Ella 和 Bella 正在参观农场。不幸的是，自从她们来到这里，就一直在搞恶作剧。

在她们最新的计划中，她们决定尽可能多地割草。农场的优质草场呈 $T\times T$ 的正方形。左下角是 $(0,0)$，右上角是 $(T,T)$。因此，这个正方形包含 $(T+1)^2$ 个格点（整数坐标的点）。

Ella 和 Bella 计划从 $(0,0)$ 开始，以单位速度跑到 $(T,T)$。同时，她们各自拿着一根非常锋利、非常有弹性的钢丝的一端。被这根线扫过的任何区域的草都会被割断。Ella 和 Bella 可能沿不同的路径跑，但她们只能向右或向上移动，并且从格点移动到格点。

贝西相当担心会有太多的草被割掉，所以她想到了一个巧妙的计划来限制 Ella 和 Bella 走的路径。有 $N$ 朵美味的花（$1\le N\le 2\cdot 10^5$）散落在草地上，每朵花都位于互不相同的格点上。贝西将挑选一个花的集合 $S$，要求 Ella 和 Bella 都要经过（所以 Ella 的路径必须经过 $S$ 中所有的花，Bella 的路径也必须经过）。为了给她们的路径增加尽可能多的途经点，Bessie 将在从 $(0,0)$ 到 $(T,T)$ 向上和向右移动路径可以到达的花朵子集中选择 $S$，使其尽可能大。

Ella 和 Bella 会最大化她们的割草量，但要受到经过 $S$ 集合中花的限制。请帮助 Bessie 选择集合 $S$，使割草量尽可能少。

输入格式

第一行包含两个整数 $N,T\ (1\le N\le 2\cdot 10^5,1\le T\le 10^6)$。

接下来 $N$ 行，每行两个整数 $x_i,y_i$，表示一朵花的位置。保证 $1\le x_i,y_i\le T-1$，并且对于所有的 $i$，没有两朵花在同一水平线或竖直线上。

输出格式

输出一行，表示最少的割草量。

5 20
19 1
2 6
9 15
10 3
13 11

117

数据范围与提示

对于至少 $20\%$ 的测试数据，有 $N\le 3200$。