「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$ 在比赛前已经被确定），在比赛结束后你的贡献值最大是多少。 ## Input 从标准输入读入数据。 **本题有多组测试数据。** 输入的第一行包含一个正整数 $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$，表示参赛选手的贡献值。 ## Output 输出到标准输出。 对于每组测试数据，输出一行一个整数，表示最大的贡献值。 [samples] ## Note **【样例解释 #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$ | $100$ | C | | $6\sim 7$ | $100$ | 无 | | $8\sim 9$ | $5\times 10^3$ | AB | | $10\sim 11$ | $5\times 10^3$ | C | | $12\sim 14$ | $5\times 10^3$ | 无 | | $15$ | $2\times10^5$ | AB | | $16\sim 18$ | $2\times10^5$ | B | | $19\sim 21$ | $2\times10^5$ | 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$。