请注意非标准内存限制。
有 $$$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$$$