← 返回题目列表

Codeforces · 2229/B

B. 绝对影院

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

你发现自己有两个正整数数组 $$$a$$$ 和 $$$b$$$,长度都是 $$$n$$$。您可以多次执行以下操作:

  • 选择一个整数 $$$i$$$ ($$$1 \le i \le n$$$) 并交换 $$$a_i$$$ 和 $$$b_i$$$。

确定以最佳方式执行运算时可达到的 $$$\max(a) + \sum^{n}_{i = 1}{b_i}$$$ 的最大值。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 数组 $$$a$$$ 和 $$$b$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_{n}$$$ ($$$1 \le a_i \le 10^9$$$)。

每个测试用例的第三行包含 $$$n$$$ 整数 $$$b_1,b_2,\ldots,b_{n}$$$ ($$$1 \le b_i \le 10^9$$$)。

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

输出

对于每个测试用例,输出 $$$\max(a) + \sum^{n}_{i = 1}{b_i}$$$ 可达到的最大值。

示例

输入
复制

4
1
2
1
1
1
2
3
1 2 3
4 5 6
4
2 3 6 7
1 4 5 8

输出
复制

3
3
18
27

注意

测试用例3: 不需要交换,所以答案是$$$\max([1, 2, 3]) + 4 + 5 + 6 = 3 + 15 = 18$$$,可以证明这是最优的。

测试用例4: 您可以通过交换索引 $$$1$$$、$$$3$$$ 和 $$$4$$$ 来实现最大值。所以我们得到:

  • $$$a = [1, 3, 5, 8]$$$
  • $$$b = [2, 4, 6, 7]$$$
给出的答案为 $$$\max([1, 3, 5, 8]) + 2 + 4 + 6 + 7 = 8 + 19 = 27$$$,可以证明这是最优的。