有一家商店,里面有$$$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 可以购买的所有对象集的最大值总和。
示例
输入复制
831 -1 13 1 22 3 13-2 5 23 1 22 3 13-1 -2 -33 1 22 3 131000000000 1000000000 10000000003 1 22 3 145 -15 10 -52 4 3 11 4 2 34-5 -5 -5 1002 3 1 44 1 2 34-1 -100 5 101 2 3 42 3 4 112-4 6 10 10 1 -8 6 2 -8 -4 0 -611 12 7 3 6 8 1 5 10 2 9 47 5 3 6 1 2 8 12 9 4 10 11
输出复制
250300000000010851424
注意
在第一个测试用例中,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$$$。