题目内容

探险家发现了一排共 $n$ 个宝箱，编号 $1$ 到 $n$，第 $i$ 个宝箱的价值为 $a_i$（可能为负数）。

探险家有两本指南，各是一个 $1\sim n$ 的排列 $p$ 与 $q$，分别代表收集顺序和清除顺序。

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

• 收集：选择一个 $t$（$1\le t\le n$），按 $p_1,p_2,\dots,p_t$ 的顺序依次收集对应宝箱，获得这些宝箱当前价值之和作为收益。
• 清除：选择一个 $u$（$1\le u\le n$），依次将宝箱 $q_1,q_2,\dots,q_u$ 的当前价值变为 $0$。

所有操作结束后，若未执行过收集操作，收益视为 $0$。

请你计算探险家能够获得的最大收益。

约束条件：

• $n$ 为正整数，单个测试点的 $n$ 之和不超过 $2\times 10^5$。
• $|a_i|\le 10^9$。
• $p$ 和 $q$ 均为 $1\sim n$ 的排列。

输入描述

第一行包含一个整数 $T$（$1 \le T \le 10^4$），表示测试数据组数。 接下来每组数据包含：

• 第一行一个整数 $n$（$1 \le n \le 2\times 10^5$），表示宝箱数量。
• 第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$（$|a_i| \le 10^9$），表示每个宝箱的初始价值。
• 第三行 $n$ 个整数 $p_1, p_2, \dots, p_n$，为 $1\sim n$ 的一个排列，表示收集顺序。
• 第四行 $n$ 个整数 $q_1, q_2, \dots, q_n$，为 $1\sim n$ 的一个排列，表示清除顺序。

保证所有测试数据的 $n$ 之和不超过 $2\times 10^5$。

输出描述

对每组数据输出一行一个整数，表示能够获得的最大收益。

样例1

输入

1
1
-2
1
1

输出

0

说明

只有 1 个宝箱，价值 $-2$，收集顺序和清除顺序均为 1。无论是否收集，收益均为 0（不收集得 0，收集得 $-2 < 0$）。因此最大收益为 0。

样例2

输入

1
3
3 -1 2
2 1 3
3 1 2

输出

4

说明

收集顺序 $p=[2,1,3]$，清除顺序 $q=[3,1,2]$。按 $p$ 重排后的序列为 $s=[h_2, h_1, h_3] = [-1, 3, 2]$，前缀和 $pre = [0, -1, 2, 4]$。初始最大前缀和为 4（收集 $t=3$）。 依次考虑清除操作：

• 清除 $q_1=3$：对应 $s$ 中位置 3，价值 $2$ 变 0，$pre$ 变为 $[0, -1, 2, 2]$，最大前缀和变为 $\\max(0, -1, 2, 2)=2$。
• 清除 $q_2=1$：对应位置 2，价值 $3$ 变 0，$pre$ 变为 $[0, -4, -1, -1]$，最大为 0。
• 清除 $q_3=2$：对应位置 1，价值 $-1$ 变 0，$pre$ 变为 $[1, -3, 0, 0]$，最大为 1。 整个过程最大收益为 $\\max(0, 4, 2, 0, 1) = 4$。所以输出 4。

样例3

输入

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

输出

9

说明

宝箱价值 $h=[-10,5,4,-1]$，收集顺序 $p=[2,1,4,3]$，清除顺序 $q=[1,4,2,3]$。重排序列 $s=[5,-10,-1,4]$，初始前缀和 $pre=[0,5,-5,-6,-2]$，最大前缀和为 5。 依次执行清除：

• 清除 $q_1=1$（$h_1=-10$，在 $s$ 中位置 2）：对区间 $[2,4]$ 加 $10$，$pre$ 变为 $[0,5,5,4,8]$，最大前缀和 8。
• 清除 $q_2=4$（$h_4=-1$，位置 3）：对 $[3,4]$ 加 $1$，$pre$ 变为 $[0,5,5,5,9]$，最大前缀和 9。
• 清除 $q_3=2$（$h_2=5$，位置 1）：对 $[1,4]$ 减 $5$，$pre$ 变为 $[0,0,0,0,4]$，最大 4。
• 清除 $q_4=3$（$h_3=4$，位置 4）：对 $[4,4]$ 减 $4$，$pre$ 末位归 0，最大 0。 全局最大值为 $\\max(0,5,8,9,4,0)=9$。先清除宝箱 1 和 4 后，剩下的序列为 $[5,0,0,4]$，收集全部可得 $9$。输出 9。