← 返回题目列表

Codeforces · 1740/B

B. 特大奶酪 2

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

Pak Chanek 有 $$$n$$$ 二维奶酪片。第 $$$i$$$ 奶酪片可以表示为尺寸为 $$$a_i \times b_i$$$ 的矩形。我们希望将它们排列在二维平面上,以便:

- 每个奶酪的每条边都平行于 x 轴或 y 轴。
- 每个奶酪的底部边缘是 x 轴的一部分。
- 两片奶酪不能重叠,但它们的侧面可以接触。
- 它们形成一个相连的形状。

请注意,我们可以按任何顺序排列它们(最左边的奶酪片不一定是第一片奶酪)。另请注意,只要所有条件仍然成立,我们就可以以任何方式旋转每片奶酪。

找到构造形状的最小可能周长。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$) — 测试用例的数量。以下行包含每个测试用例的描述。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — Pak Chanek 拥有的奶酪片数。

每个测试用例接下来的 $$$n$$$ 行的第 $$$i$$$ 行包含两个整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \leq a_i,b_i \leq 10^9$$$) — 第 $$$i$$$ 奶酪片的尺寸。

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

输出

对于每个测试用例,输出一行包含一个整数,表示所构造形状的最小可能周长。

示例

输入 #1

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

输出 #1

26
24
134

注意

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

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

考虑以下无效排列。

尽管上面形状的周长是 $$$24$$$,但它并不能满足问题的所有条件。 $$$1 \times 1$$$ 奶酪片的底边不是 x 轴的一段。

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

我们可以计算出所构造形状的周长为$$$2+2+2+3+2+3+2+2+2+4=24$$$。可以证明我们无法得到更小的周长。