您正在为一个无限方形网格着色,其中所有单元格最初都是白色的。为此,您将获得 $$$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$$$。