Responsive image

问题 2733 --巨无霸特级奶酪

2733: 巨无霸特级奶酪

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 26
[提交][状态][讨论版][命题人:]

题目描述

Pak Chanek有n个二维奶酪片。第i片奶酪可以表示为一个尺寸为ai×bi的矩形。我们想把它们安排在二维平面上，这样。

每块奶酪的每条边都平行于X轴或Y轴。
每块奶酪的底边是x轴的一段。
没有两片奶酪重叠，但它们的边可以接触。
它们形成一个相连的形状。
请注意，我们可以以任何顺序排列它们（最左边的那片奶酪不一定是第一片奶酪）。还要注意的是，我们可以以任何方式旋转每片奶酪，只要所有的条件仍然成立。

找出所建图形的最小可能周长。

输入描述

每个测试包含多个测试用例。第一行包含一个整数t（1≤t≤2⋅104）--测试用例的数量。下面几行包含每个测试用例的描述。

每个测试用例的第一行包含一个整数n (1≤n≤2⋅109)--Pak Chanek的奶酪片的数量。

每个测试案例接下来的n行中的第i行包含两个整数ai和bi（1≤ai,bi≤1010）--第i片奶酪的尺寸。

可以保证所有测试用例的n之和不超过2⋅105。

输出描述

对于每个测试案例，输出一条包含整数的值，代表构建的形状的最小可能周长。

样例输入

3
4
4 1
4 5
1 1
2 3
3
2 4
2 6
2 3
1
2 65

样例输出

26
24
134

提示

在第一个测试用例中，获得最小周长的一种方法是按如下方式排列奶酪片。



我们可以计算出构造形状的周长为2+5+1+1+1+1+1+3+1+5+1+2+3=26可以证明，我们不能得到更小的周长。

请考虑以下无效安排。







即使上面形状的周长是24，它不满足问题的所有条件。底部边缘1 x 1奶酪片不是 X轴的一部分。



在第二个测试用例中，获得最小周长的一种方法是按如下方式排列奶酪片。







我们可以计算出构造形状的周长为2+2+2+3+2+3+2+2+2+4=24.可以证明，我们不能得到更小的周长。


来源

21数一马宜洛  

[提交][状态]
ACM算法攻关部