5157. 模后和

单点时限: 1.0 sec

内存限制: 128 MB

HMP_Haoge 编写了一款开放世界游戏。游戏中有一个关于战斗的小游戏,首先玩家拥有 $n$ 个战士,它们的战斗力分别为 $a_1,a_2,\cdots a_n$ ;接着,玩家拥有 $n$ 个辅助,它们的辅助力分别为 $b_1,b_2,\cdots b_n$ 。

现在,玩家需要将这 $2n$ 个角色分为 $n$ 组,每组为一个战士和一个辅助,每组的战斗力为组内战士战斗力和辅助的辅助力之和。然而,开发者在开发时不小心写了一个bug,它将每个组的战斗力对 $n$ 进行了取模。形式化来说,对于第 $x$ 组,我们记该组的战斗力为 $c_x$,假设该组由第 $i$ 个战士和第 $j$ 个辅助组成,那么 $c_x = (a_i+b_j) \mod n$。

你发现了这个bug,但是你却无法改变它,这时你作为玩家,你希望完成分组,并且使得所有组的战斗力之和最大,即最大化 $\sum _{x=1}^{n}c_x$。

你只需要输出这个最大的战斗力之和即可。

输入格式

首先输入一个正整数 $T$ ,表示数据组数。

对于每组数据:

第一行,一个整数 $n$ 表示战士和辅助的数目;

第二行, $n$ 个整数,第 $i$ 个数表示 $a_i$ ;

第三行, $n$ 个整数,第 $i$ 个数表示$ b_i$ ;

保证 $T$ 组测试数据的 $\sum n$ 不超过 $2\times 10^5$ 。

输出格式

对于每组数据,输出一行,一个整数,表示最大的$\sum_{i=1}^nc_i$

样例

Input
2
4
31 45 92 65
35 89 79 32
10
1 1 4 5 1 4 1 1 4 5
1 9 1 9 8 1 0 1 9 1
Output
8
37

提示

【样例解释】

用二元组 $(i,j)$ 表示把 $a_i$ 和 $b_j$ 分为一组。

那么对于第一组数据,可以采用的分组方案为:$(1,3),(2,4),(3,1),(4,2)$

此时得到最大的战斗力和为:

${(31+79)\mod 4} + {(45+32)\mod 4} + {(92+35)\mod 4} + {(65+89)\mod 4} =2+1+3+2=8$

【数据范围】

$1\le T \le 2\times 10^5$

$1\le n\le 2\times 10^5,\sum n \le 2\times 10^5$,$0\le a_i,b_i \le 2\times 10^5$

107 人解决,165 人已尝试。

120 份提交通过,共有 689 份提交。

4.2 EMB 奖励。

创建: 1 年,4 月前.

修改: 1 年,4 月前.

最后提交: 8 月前.

来源: N/A

题目标签