题目内容

有两个长度均为 $n$ 的非负整数序列 $p_1, p_2, \dots, p_n$ 和 $q_1, q_2, \dots, q_n$。每次操作只能将某个元素的值减少 $1$，且不能对已经是 $0$ 的元素执行操作。允许的操作有三种：

• 选择一个下标 $i$，将 $p_i$ 减少 $1$；
• 选择一个下标 $j$，将 $q_j$ 减少 $1$；
• 选择两个下标 $i,j$（允许 $i = j$），同时将 $p_i$ 和 $q_j$ 各减少 $1$。

目标是通过若干次操作，使得对于所有 $1 \le i \le n$ 都有 $p_i = q_i$。请计算达成目标所需的最少操作次数。

约束：单个测试文件中最多包含 $T = 2 \times 10^5$ 组数据。每组数据中序列长度 $n$ 不超过 $2 \times 10^5$，且所有数据的 $n$ 之和也不超过 $2 \times 10^5$。序列中的每个元素均为非负整数且不超过 $10^9$。

输入描述

第一行包含一个整数 $T$，表示测试数据的组数。接下来依次描述每组数据：

每组数据的第一行包含一个整数 $n$，表示序列的长度； 第二行包含 $n$ 个整数，依次为 $p_1, p_2, \dots, p_n$； 第三行包含 $n$ 个整数，依次为 $q_1, q_2, \dots, q_n$。

输出描述

对于每组测试数据，输出一行一个整数，表示最少的操作次数。

样例1

输入

1
4
10 20 30 40
10 20 30 40

输出

0

说明

所有位置上 $p_i$ 与 $q_i$ 均相等，最终值可以保持为 $c_i = p_i = q_i$，不需要执行任何操作。最少操作次数为 0。

样例2

输入

1
3
1 5 2
3 2 4

输出

4

说明

逐位比较：

• $i=1$: $p_1=1 < q_1=3$，必须从 $q_1$ 单独减掉 2，计入 $needB$；
• $i=2$: $p_2=5 > q_2=2$，必须从 $p_2$ 单独减掉 3，计入 $needA$；
• $i=3$: $p_3=2 < q_3=4$，必须从 $q_3$ 单独减掉 2，计入 $needB$。 因此 $needA = 3$，$needB = 2+2 = 4$。操作 3 可以同时消耗两边需求，最少操作次数为 $\max(3, 4) = 4$。

样例3

输入

2
2
0 0
0 0
2
7 0
0 3

输出

0
7

说明

第一组数据：两个序列完全相同，$needA = 0$，$needB = 0$，最少操作次数为 0。

第二组数据：$p = [7, 0]$，$q = [0, 3]$。对于 $i=1$，$7 > 0$，$needA$ 累加 7；对于 $i=2$，$0 < 3$，$needB$ 累加 3。因此 $needA = 7$，$needB = 3$，最少操作次数为 $\max(7, 3) = 7$。

样例4

输入

1
1
1000000000
0

输出

1000000000

说明

序列长度 $n = 1$，$p_1 = 10^9$，$q_1 = 0$。最终两者必须相等且都只能减少，因此 $p_1$ 必须降至 0。由于 $q_1$ 已经为 0，不能再减少，操作 3（同时减少 $p_i$ 和 $q_j$）中涉及 $q_1$ 的部分无法执行。因此只能通过 $10^9$ 次操作 1 单独将 $p_1$ 减为 0。最少操作次数为 1000000000。