题目描述

输入两个长度都为 $n$ 的序列 $a_1,a_2,\ldots, a_n$ 和 $b_1,b_2,\ldots,b_n$，定义这两个序列的权值为

$\sum\limits_{i=1}^{n} \left| a_i - b_i \right|$

其中 $|\cdot|$ 是绝对值符号。

你可以选择两个位置 $i,j (i \ne j)$，然后交换 $b_i$ 和 $b_j$。这个操作最多只能做一次。你需要使得上述式子的值最大化，请求出这个最大值是多少？

输入格式

第一行一个正整数 $T$，表示数据组数。

接下来对于每一组数据，第一行输入一个正整数 $n$，表示序列长度；第二行输入 $n$ 个正整数 $a_1,a_2,\ldots,a_n$；第三行输入 $n$ 个正整数 $b_1,b_2,\ldots,b_n$。

输出格式

对于每一组数据，输出题面中要求的式子的最大值。输出一行一个整数。

输入样例

6
3
1 3 5
3 3 3
2
1 2
1 2
2
1 2
2 1
4
1 2 3 4
5 6 7 8
10
1 8 2 5 3 5 3 1 1 3
2 9 2 4 8 2 3 5 3 1
3
47326 6958 358653
3587 35863 59474

输出样例

4
2
2
16
31
419045

说明提示

样例解释

对于第一组数据，无论怎么交换都不会使得该式子的值增大。

对于第二组数据，交换这两个数之后的式子的值为 $2$，交换之前为 $0$。

对于第三组数据，请注意交换操作只是最多操作一次，而不是必须操作。

输入样例 #2

1
2
640738217 218453644
182116583 884409125

输出样例 #2

1124577115

输入样例 #3

1
3
199347761 909406715 206515710
216605533 736698794 623856393

输出样例 #3

1647492898

数据范围

• 对于 $30\%$ 的数据，$2 \le n \le 100$，单个测试点 $\sum n \le 100$

• 对于 $60\%$ 的数据，$2 \le n \le 2000$，单个测试点 $\sum n \le 2000$

• 对于 $100\%$ 的数据，$2 \le n \le 2\cdot 10^5$，单个测试点 $\sum n \le 10^6$，$1\le a_i,b_i \le 10^9$，$1\le T \le 10^4$。