「KDOI-06-J」贡献系统

题目描述

洛谷贡献系统上线了！

现在有 $n$ 个人即将参加一场洛谷月赛，每个人的等级分互不相同。第 $i$ 个人的等级分是 $r_i$，贡献值是 $c_i$。

假设第 $i$ 个人的等级分在这 $n$ 个人中的排名是 $a_i$（排名按等级分从大到小排序），且在月赛中的排名是 $b_i$，没有两个人的排名相同。也就是说，$a$ 和 $b$ 都是 $1$ 到 $n$ 的排列。比赛结束后，每个人都会执行以下操作：

• 若 $a_i=b_i$，则第 $i$ 个人的等级分不会发生任何变化，因此第 $i$ 个人不会进行任何操作；
• 若 $a_i>b_i$，则第 $i$ 个人的等级分会上升，因此第 $i$ 个人会给出题人点赞，导致出题人的贡献值上升 $c_i$（$c_i$ 可能是负数，此时会导致出题人的贡献值下降）；
• 若 $a_i<b_i$，则第 $i$ 个人的等级分会下降，因此第 $i$ 个人会给出题人点踩，导致出题人的贡献值下降 $c_i$（$c_i$ 可能是负数，此时会导致出题人的贡献值上升）。

作为这场月赛唯一的出题人，初始时你的贡献值为 $0$。你想知道，对于所有可能的排列 $b$（显然，排列 $a$ 在比赛前已经被确定），在比赛结束后你的贡献值最大是多少。

输入格式

从标准输入读入数据。

本题有多组测试数据。

输入的第一行包含一个正整数 $T$，表示数据组数。

对于每组测试数据，第一行一个正整数 $n$，表示参赛选手人数。

第二行包含 $n$ 个非负整数 $r_1,r_2,\ldots,r_n$，表示参赛选手的等级分。保证对于任意 $1\le i< n$，$r_i>r_{i+1}$。

第三行包含 $n$ 个整数 $c_1,c_2,\ldots,c_n$，表示参赛选手的贡献值。

输出格式

输出到标准输出。

对于每组测试数据，输出一行一个整数，表示最大的贡献值。

样例 #1

样例输入 #1

3
5
3816 3738 3726 3621 3582
111 109 -50 -22 208
8
8 7 6 5 4 3 2 1
128 1 0 0 0 0 1 0
10
10 9 8 7 6 5 4 3 2 1
1 1 4 5 1 4 1 9 1 9

样例输出 #1

280
1
34

提示

【样例解释 #1】

对于第一组测试数据，设五个人按输入顺序分别为 A，B，C，D，E，则当月赛中的排名顺序为 ABECD 时贡献值最大，为 $0+0-(-50)-(-22)+208=280$。可以证明，这是唯一能使贡献值达到最大的排名顺序。

对于第二组测试数据，设八个人按输入顺序分别为 A，B，C，D，E，F，G，H，则当月赛中的排名顺序为 ABCDEGFH 时可以使贡献值达到最大值 $1$，注意此时有多种可能的使贡献值最大的排名顺序。

【样例 #2】

见选手目录下的 contrib/contrib2.in 与 contrib/contrib2.ans。

【样例 #3】

见选手目录下的 contrib/contrib3.in 与 contrib/contrib3.ans。

---

【数据范围】

对于所有数据保证：$1\le T\le 5$，$1\le n\le 2\times 10^5$，$0\le r_i\le 10^9$，$-10^9\le c_i\le 10^9$，且对于任意 $1\le i<n$，$r_i>r_{i+1}$。

测试点编号	$n\le$	特殊限制
$1\sim3$	$8$	无
$4$	$100$	ABC
$5$		C
$6\sim 7$		无
$8\sim 9$	$5\times 10^3$	AB
$10\sim 11$		C
$12\sim 14$		无
$15$	$2\times10^5$	AB
$16\sim 18$		B
$19\sim 21$		C
$22\sim 25$	$2\times 10^5$	无

• 特殊性质 A：对于任意 $1\le i<n$，保证 $c_i=c_{i+1}$；
• 特殊性质 B：对于任意 $1\le i<n$，保证 $c_i\le c_{i+1}$；
• 特殊性质 C：对于任意 $1\le i\le n$，保证 $c_i\ge 0$。