解题思路

设按排列 $b$ 取出的顺序对应的数列为

那么第一种操作“选择一个整数 $x$，获得权值 $\sum_{i=1}^{x} a_{b_i}$”，本质上就是：

题目内容

给定一个长度为 $n$ 的整数数组 $a_1,a_2,…,a_n$，以及两个长度为 n 的排列$b_1,b_2,…,b_n$ 与 $c_1,c_2,…,c_n$。

你可以至多各执行一次下列两种操作，执行顺序可以任意：

1. 选择一个整数 $x(1≤x≤n)$，获得权值 $∑_{i=1}^xa_{b_i}$；
2. 选择一个整数$y(1≤y≤n)$，依次将 $a_{c_1},a_{c_2},…,a_{c_y}$ 修改为 $0$。

你也可以选择不执行其中某个操作；若两种操作均不执行，则权值为$0$。

请输出能够获得的最大权值。

排列：长度为 $n$ 的排列是由 $1$∼$n$ 这$n$ 个整数按任意顺序组成的数组，其中每个整数恰好出现一次。。

输入描述

每个测试文件均包含多组测试数据：第一行输入一个整数 $T(1≤T≤10^4)$，代表数据组数。每组测试数据描述如下：

• 第一行输入一个整数 $n(1≤n≤2×10^5)$，表示数组和排列的长度；

• 第二行输入$n$个整数 $a_1,a_2,…,a_n(−10^9≤a_i≤10^9)$，表示数组$a$；

• 第三行输入 $n$个整数$b_1,b_2,…,b_n(1≤b_i≤n)$，表示排列$b$；

• 第四行输入 $n$ 个整数 $c_1,c_2,…,c_n(1≤c_i≤n)$，表示排列$c$。

  除此之外，保证单个测试文件的 $n$ 之和不超过 $2×10^5$。

输出描述

对于每一组测试数据，新起一行，输出一个整数，表示能够获得的最大权值。

样例1

输入

3
3
2 -3 4
1 3 2
2 1 3
4
5 -10 6 3
1 2 3 4
2 4 1 3
1
-1
1
1

输出

6
14
0

说明

• 在第二组样例中：若先选择$y=1$，将 $a_2$ 置为$0$，得到数组$a=[5,0,6,3]$；随后选择 $x=4$，可获得权值 $\sum ^4a_{b_i}=5+0+6+3=14$；这是本组数据的最优解。