← 返回题目列表

Codeforces · 2027/A

A. 矩形排列

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

您正在为一个无限方形网格着色,其中所有单元格最初都是白色的。为此,您将获得 $$$n$$$ 邮票。每个图章都是一个宽度为 $$$w_i$$$ 且高度为 $$$h_i$$$ 的矩形。

您将仅使用每个图章一次,将网格上与图章大小相同的矩形着色为黑色。您无法旋转图章,并且对于每个单元格,图章必须完全覆盖它或根本不覆盖它。您可以在网格上的任何位置使用图章,即使被图章区域覆盖的部分或全部单元格已经是黑色的。

使用完所有印章后,您可以获得的黑色方块相连区域的周长最小和是多少?

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 500$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$)。

接下来的 $$$n$$$ 行的第 $$$i$$$ 行包含两个整数 $$$w_i$$$ 和 $$$h_i$$$ ($$$1 \le w_i, h_i \le 100$$$)。

输出

对于每个测试用例,输出一个整数 - 使用所有图章后可以获得的黑色正方形连接区域周长的最小和。

示例

输入 #1

5
5
1 5
2 4
3 3
4 2
5 1
3
2 2
1 1
1 2
1
3 2
3
100 100
100 100
100 100
4
1 4
2 3
1 5
3 2

输出 #1

20
8
10
400
16

注意

在第一个测试用例中,可以使用如左图所示的标记。为了清晰起见,每个邮票都以其自己的颜色突出显示。

这些印章全部用完后,会出现一个黑色区域(如右图),其周长为$$$20$$$。可以看出,没有办法使用产生较低总周长的印章。

在第二个测试用例中,第二个和第三个图章可以完全在第一个图章内部使用,因此最小周长等于 $$$8$$$。