← 返回题目列表

Codeforces · 1497/D

D. 天才

中文机器翻译题面 查看原题

请注意非标准内存限制。

有 $$$n$$$ 问题,编号为从 $$$1$$$ 到 $$$n$$$ 的整数。第 $$$i$$$ 问题的复杂度为 $$$c_i = 2^i$$$,标签为 $$$tag_i$$$,得分为 $$$s_i$$$。

解决问题 $$$i$$$ 后,当且仅当 $$$\text{IQ} < |c_i - c_j|$$$ 且 $$$tag_i \neq tag_j$$$ 时,才允许解决问题 $$$j$$$。解决该问题后,您的 $$$\text{IQ}$$$ 会发生变化并变为 $$$\text{IQ} = |c_i - c_j|$$$ 并且您将获得 $$$|s_i - s_j|$$$ 分。

有什么问题都可以先来。您可以按任意顺序解决问题,并且可以根据需要多次解决问题。

最初你的$$$\text{IQ} = 0$$$。找出可以获得的最大积分。

输入

第一行包含一个整数 $$$t$$$ $$$(1 \le t \le 100)$$$ — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ $$$(1 \le n \le 5000)$$$ — 问题数。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$tag_1, tag_2, \ldots, tag_n$$$ $$$(1 \le tag_i \le n)$$$ — 问题的标签。

每个测试用例的第三行包含 $$$n$$$ 整数 $$$s_1, s_2, \ldots, s_n$$$ $$$(1 \le s_i \le 10^9)$$$ — 问题的分数。

保证所有测试用例的$$$n$$$总和不超过$$$5000$$$。

输出

对于每个测试用例,打印一个整数 - 可以获得的最大分数。

示例

输入 #1

5
4
1 2 3 4
5 10 15 20
4
1 2 1 2
5 10 15 20
4
2 2 4 1
2 8 19 1
2
1 1
6 9
1
1
666

输出 #1

35
30
42
0
0

注意

在第一个测试用例中解决问题的最佳顺序如下:

1. $$$1 \rightarrow 2$$$,之后总分为 $$$5$$$ 且 $$$\text{IQ} = 2$$$
2. $$$2 \rightarrow 3$$$,之后总分为 $$$10$$$ 且 $$$\text{IQ} = 4$$$
3. $$$3 \rightarrow 1$$$,之后总分为 $$$20$$$ 且 $$$\text{IQ} = 6$$$
4. $$$1 \rightarrow 4$$$,之后总分为 $$$35$$$ 且 $$$\text{IQ} = 14$$$

在第二个测试用例中解决问题的最佳顺序如下:

1. $$$1 \rightarrow 2$$$,之后总分为 $$$5$$$ 且 $$$\text{IQ} = 2$$$
2. $$$2 \rightarrow 3$$$,之后总分为 $$$10$$$ 且 $$$\text{IQ} = 4$$$
3. $$$3 \rightarrow 4$$$,之后总分为 $$$15$$$ 且 $$$\text{IQ} = 8$$$
4. $$$4 \rightarrow 1$$$,之后总分为 $$$35$$$ 且 $$$\text{IQ} = 14$$$

在第三个测试用例中解决问题的最佳顺序如下:

1. $$$1 \rightarrow 3$$$,之后总分为 $$$17$$$ 且 $$$\text{IQ} = 6$$$
2. $$$3 \rightarrow 4$$$,之后总分为 $$$35$$$ 且 $$$\text{IQ} = 8$$$
3. $$$4 \rightarrow 2$$$,之后总分为 $$$42$$$ 并且 $$$\text{IQ} = 12$$$