#L9742. 洛谷模拟「KDOI-06-J」贡献系统

洛谷模拟「KDOI-06-J」贡献系统

「KDOI-06-J」贡献系统

题目描述

洛谷贡献系统上线了!

现在有 nn 个人即将参加一场洛谷月赛,每个人的等级分互不相同。第 ii 个人的等级分是 rir_i,贡献值是 cic_i

假设第 ii 个人的等级分在这 nn 个人中的排名是 aia_i(排名按等级分从大到小排序),且在月赛中的排名是 bib_i,没有两个人的排名相同。也就是说,aabb 都是 11nn 的排列。比赛结束后,每个人都会执行以下操作:

  • ai=bia_i=b_i,则第 ii 个人的等级分不会发生任何变化,因此第 ii 个人不会进行任何操作;
  • ai>bia_i>b_i,则第 ii 个人的等级分会上升,因此第 ii 个人会给出题人点赞,导致出题人的贡献值上升 cic_icic_i 可能是负数,此时会导致出题人的贡献值下降);
  • ai<bia_i<b_i,则第 ii 个人的等级分会下降,因此第 ii 个人会给出题人点踩,导致出题人的贡献值下降 cic_icic_i 可能是负数,此时会导致出题人的贡献值上升)。

作为这场月赛唯一的出题人,初始时你的贡献值为 00。你想知道,对于所有可能的排列 bb(显然,排列 aa 在比赛前已经被确定),在比赛结束后你的贡献值最大是多少。

输入格式

从标准输入读入数据。

本题有多组测试数据。

输入的第一行包含一个正整数 TT,表示数据组数。

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

第二行包含 nn 个非负整数 r1,r2,,rnr_1,r_2,\ldots,r_n,表示参赛选手的等级分。保证对于任意 1i<n1\le i< nri>ri+1r_i>r_{i+1}

第三行包含 nn 个整数 c1,c2,,cnc_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=2800+0-(-50)-(-22)+208=280。可以证明,这是唯一能使贡献值达到最大的排名顺序。

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

【样例 #2】

见选手目录下的 contrib/contrib2.incontrib/contrib2.ans

【样例 #3】

见选手目录下的 contrib/contrib3.incontrib/contrib3.ans


【数据范围】

对于所有数据保证:1T51\le T\le 51n2×1051\le n\le 2\times 10^50ri1090\le r_i\le 10^9109ci109-10^9\le c_i\le 10^9,且对于任意 1i<n1\le i<nri>ri+1r_i>r_{i+1}

测试点编号 nn\le 特殊限制
131\sim3 88
44 100100 ABC
55 C
676\sim 7
898\sim 9 5×1035\times 10^3 AB
101110\sim 11 C
121412\sim 14
1515 2×1052\times10^5 AB
161816\sim 18 B
192119\sim 21 C
222522\sim 25 2×1052\times 10^5
  • 特殊性质 A:对于任意 1i<n1\le i<n,保证 ci=ci+1c_i=c_{i+1}
  • 特殊性质 B:对于任意 1i<n1\le i<n,保证 cici+1c_i\le c_{i+1}
  • 特殊性质 C:对于任意 1in1\le i\le n,保证 ci0c_i\ge 0