#1034. 绝对值

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: tony102

题目描述

输入两个长度都为 的序列 ,定义这两个序列的权值为

其中 是绝对值符号。

你可以选择两个位置 ,然后交换 。这个操作最多只能做一次。你需要使得上述式子的值最大化,请求出这个最大值是多少?

输入格式

第一行一个正整数 ,表示数据组数。

接下来对于每一组数据,第一行输入一个正整数 ,表示序列长度;第二行输入 个正整数 ;第三行输入 个正整数

输出格式

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

样例

样例输入

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

样例解释

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

对于第二组数据,交换这两个数之后的式子的值为 ,交换之前为

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

数据范围与提示

  • 对于 的数据,,单个测试点

  • 对于 的数据,,单个测试点

  • 对于 的数据,,单个测试点