← 返回题目列表

Codeforces · 1879/B

B. 板上的芯片

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

给你一个大小为 $$$n \times n$$$ 的棋盘($$$n$$$ 行和 $$$n$$$ 列)和两个大小为 $$$n$$$ 的正整数数组 $$$a$$$ 和 $$$b$$$。

您的任务是将筹码放置在该板上,以便每个单元 $$$(i, j)$$$ 满足以下条件:

- 与单元格 $$$(i, j)$$$ 同一列或同一行中至少存在一个筹码。 IE。存在一个单元$$$(x, y)$$$,使得该单元中有一个芯片,并且$$$x = i$$$ 或$$$y = j$$$(或两者)。

将芯片放入单元 $$$(i, j)$$$ 中的成本等于 $$$a_i + b_j$$$。

例如,对于 $$$n=3$$$、$$$a=[1, 4, 1]$$$ 和 $$$b=[3, 2, 2]$$$。一种可能的芯片布局如下:

白色方块为空

该展示位置的总成本为 $$$(1+3) + (1+2) + (1+2) = 10$$$。

根据上述规则计算出可能投入筹码的最小总成本。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$)。

第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 10^9$$$)。

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

输出

对于每个测试用例,打印一个整数 - 根据规则放置筹码的最小可能总成本。

示例

输入 #1

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

输出 #1

10
9
13
24

注意

示例的第一个测试用例在语句中进行了描述。