#P5244. [USACO19FEB] Mowing Mischief P

[USACO19FEB] Mowing Mischief P

题目描述

Bessie 的表妹 Ella 和 Bella 正在参观农场。不幸的是,自从他们到达以来,他们一直在恶作剧。

在他们的最新计划中,他们决定尽可能多地割草。农场的草地是 T×T T \times T 的正方形。左下角是 (0,0) (0,0) ,右上角是 (T,T) (T,T) 。因此,正方形包含 (T+1)2 (T+1)^2 个格点(具有整数坐标的点)。

Ella 和 Bella 计划从 (0,0) (0,0) 开始并以每秒一个单位长度的速度运行到 (T,T) (T,T) ,同时每只奶牛都握住非常锋利且非常有弹性的线的一端。任何被这根电线扫过的区域的草都会被切断。Ella 和 Bella 可能采取不同的路径,但她们只会向上或者向右移动,从一个格点移动到另一个格点。

Bessie 非常担心会切割太多的草,所以她发明了一个聪明的计划来限制 Ella 和 Bella 的路径。在整个草原上散布着 N N 种花( 1N2×105 1 \leq N \leq 2 \times 10^5 ),每种花都在一个特定的格点上。 Bessie 将从这些花中挑选一个子集 S S S S 集合中的花 Ella 和 Bella 都需要经过(Ella 和 Bella 的路径都必须经过 S S 中的所有花朵)。

Ella 和 Bella 将会切割面积尽可能大的草,请帮助Bessie确定集合 S S 使得在 S S 集合尽可能大的情况下被切割的草的面积最小。

输入格式

输入第一行包括两个数 N,T N,T 1T1061 \leq T \leq 10^6)。

接下来 N N 行每行包含两个数 xi,yi x_i,y_i ,代表一种花的位置。

保证 1xi,yiT1 1 \leq x_i,y_i \leq T-1 ,且不存在两朵花在同一条水平或竖直线上。

输出格式

输出一个整数,即被切割的草的面积的最小值。

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

提示

选择 (10,3) (10,3) (13,11) (13,11) 这两个位置上的花,可以使得被切割的草的面积最小。

子任务:对于 20% 20\% 的数据, N3200 N \leq 3200