← 返回题目列表

Codeforces · 1976/B

B. 增加/减少/复制

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

给定两个整数数组:长度为 $$$n$$$ 的数组 $$$a$$$ 和长度为 $$$n+1$$$ 的数组 $$$b$$$。

您可以按任意顺序执行以下操作任意次数:

- 选择数组 $$$a$$$ 的任意元素并将其增加 $$$1$$$;
- 选择数组 $$$a$$$ 的任意元素并将其减少 $$$1$$$;
- 选择数组 $$$a$$$ 的任意元素,复制它并将副本附加到数组 $$$a$$$ 的末尾。

您的任务是计算将数组 $$$a$$$ 转换为数组 $$$b$$$ 所需的最少上述操作数(可能为零)。可以证明,在问题的约束下,总是可能的。

输入

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

每个测试用例由三行组成:

- 第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$);
- 第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$);
- 第三行包含 $$$n + 1$$$ 整数 $$$b_1, b_2, \dots, b_{n + 1}$$$ ($$$1 \le b_i \le 10^9$$$)。

对输入的附加约束:所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数 - 将数组 $$$a$$$ 转换为数组 $$$b$$$ 所需的最小操作数(可能为零)。

示例

输入 #1

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

输出 #1

3
1
8

注意

在第一个示例中,您可以将 $$$a$$$ 转换为 $$$b$$$,如下所示:$$$[2] \rightarrow [2, 2] \rightarrow [1, 2] \rightarrow [1, 3]$$$。