← 返回题目列表

Codeforces · 2114/D

D. 靠近一点

中文机器翻译题面 查看原题

游戏场是一个大小为 $$$10^9 \times 10^9$$$ 的矩阵,其中第 $$$a$$$ 行和第 $$$b$$$ 列的交叉点处有一个单元格,表示为 ($$$a, b$$$)。

游戏场上有$$$n$$$个怪物,第$$$i$$$个怪物位于单元格($$$x_i, y_i$$$)内,而其他单元格为空。一个单元格中最多只能有一个怪物。

你可以将一只怪兽移动到场上没有被其他怪兽占据的任意格子上 最多一次 .

之后,您必须选择 一 场地上的矩形;所选矩形内的所有怪物都将被消灭。您必须为所选矩形中的每个单元格支付 $$$1$$$ 硬币。

你的任务是找到消灭所有怪物所需的最少硬币数量。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 场上的怪物数量。

以下 $$$n$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i, y_i \le 10^9$$$) — 第 $$$i$$$ 个怪物所在单元格的坐标。所有对 ($$$x_i, y_i$$$) 都是不同的。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数 - 摧毁所有 $$$n$$$ 怪物的最低成本。

示例

输入
复制

7
3
1 1
1 2
2 1
5
1 1
2 6
6 4
3 3
8 2
4
1 1
1 1000000000
1000000000 1
1000000000 1000000000
1
1 1
5
1 2
4 2
4 3
3 1
3 2
3
1 1
2 5
2 2
4
4 3
3 1
4 4
1 2

输出
复制

3
32
1000000000000000000
1
6
4
8

注意

下面是最佳移动的示例,其中要选择的矩形单元格以绿色突出显示。

第一个示例所需的移动。
第五个示例所需的移动。