← 返回题目列表

Codeforces · 2150/C

C. 限量版店

中文机器翻译题面 查看原题
cYsmix - 有腿的房子
⠀

有一家商店,里面有$$$n$$$个物品,编号从$$$1$$$到$$$n$$$,每个物品只有一份。根据您的说法,对象的值为 $$$v_1、v_2、\ldots、v_n$$$ (可以为负数)。

Alice 和 Bob 有自己的对象偏好顺序(分别为 $$$a_1、a_2、\ldots、a_n$$$ 和 $$$b_1、b_2、\ldots、b_n$$$)。特别地,Alice最喜欢的对象是$$$a_1$$$,其次是$$$a_2$$$,等等; Bob 最喜欢的对象是 $$$b_1$$$,其次是 $$$b_2$$$,依此类推。

其中一个人去商店花了 $$$n$$$ 次,购买了她或他仍在商店里最喜欢的物品。最后,爱丽丝和鲍勃拥有了自己的一组对象。

现在商店空无一人,您想知道爱丽丝的喜好是否与您相似。在爱丽丝可以购买的所有物品中,您认为最大的价值总和是多少?

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 对象的数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$v_1, v_2, \ldots, v_n$$$ ($$$-10^9 \le v_i \le 10^9$$$) - 根据您的说法,对象的值。

每个测试用例的第三行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) - Alice 的偏好顺序。 $$$a_i$$$ 是不同的。

每个测试用例的第四行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le n$$$) - Bob 的偏好顺序。 $$$b_i$$$ 是不同的。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数:Alice 可以购买的所有对象集的最大值总和。

示例

输入
复制

8
3
1 -1 1
3 1 2
2 3 1
3
-2 5 2
3 1 2
2 3 1
3
-1 -2 -3
3 1 2
2 3 1
3
1000000000 1000000000 1000000000
3 1 2
2 3 1
4
5 -15 10 -5
2 4 3 1
1 4 2 3
4
-5 -5 -5 100
2 3 1 4
4 1 2 3
4
-1 -100 5 10
1 2 3 4
2 3 4 1
12
-4 6 10 10 1 -8 6 2 -8 -4 0 -6
11 12 7 3 6 8 1 5 10 2 9 4
7 5 3 6 1 2 8 12 9 4 10 11

输出
复制

2
5
0
3000000000
10
85
14
24

注意

在第一个测试用例中,Alice 可以购买对象集 $$$[]$$$(空)、$$$[1]$$$、$$$[3]$$$、$$$[3, 1]$$$、$$$[3, 1, 2]$$$(对象按购买时间排序)。例如,Alice要购买$$$[1]$$$,两人可以按以下顺序进入商店:

  • Bob 进入并购买对象 $$$2$$$;
  • Bob 进入并购买了对象 $$$3$$$(对象 $$$2$$$ 已售完);
  • Alice 进入并购买了对象 $$$1$$$(对象 $$$3$$$ 已售完)。

根据您的判断,总价值最大的对象集合是 $$$[3, 1]$$$,其价值为 $$$v_3 + v_1 = 2$$$。

在第二个测试用例中,Alice 和 Bob 的偏好与第一个测试用例中的相同,但现在总价值最大的对象集是 $$$[3, 1, 2]$$$,价值 $$$5$$$。