题目描述

沙季正在用悠太推荐的方法做现代文阅读练习。

有 $n$ 个历史事件，编号为 $1$ 至 $n$，其中每个历史事件可能有一个编号比它更小的前置事件，也可能没有。形式化地，对于事件 $i$，用 $p_i$ 表示其前置事件的编号，满足 $p_i<i$，若 $p_i=0$ 则表示它没有前置事件。

沙季有两种方式记起一个历史事件：回想和联想。如果她进行回想，那么她可以花费 $r_u$ 时间，直接记起任意一个历史事件 $u$；如果她进行联想，那么她可以选择任意一个已经记起来的事件 $u$，并花费 $t_v$ 时间记起一个满足 $p_v=u$ 的事件 $v$。

但是她的脑容量有限，因此她最多只能同时记起 $k$ 个事件。她已经记起来的事件可以选择在任意时刻忘记，忘记事件不需要花费时间。为了防止记忆混乱，她不会再次记起任何曾经忘记过的事件。

现在，她有 $m$ 道阅读题，解决其中的第 $i$ 道题需要她记起事件 $x_i$，她可以在记起事件 $x_i$ 的时候立刻解决第 $i$ 道题目，花费的时间忽略不计。她想要知道她至少需要花费多少时间才能解决所有题目。

输入格式

第一行输入一个整数 $T$ 表示数据组数。

对于每组数据，第一行输入三个整数 $n,m,k$ 表示历史事件数量，阅读题的数量和她最多能够同时记起的事件数量。

第二行输入 $n$ 个整数，表示 $p_1,\dots,p_n$。

第三行输入 $n$ 个整数，表示 $r_1,\dots,r_n$。

第四行输入 $n$ 个整数，表示 $t_1,\dots,t_n$。保证 $p_i=0$ 时有 $t_i=0$。

第五行输入 $m$ 个整数，表示 $x_1,\dots,x_m$。

输出格式

对于每组数据，输出一行一个整数，表示为了解决所有问题至少需要花费的总时间。

2
5 3 3
0 1 1 0 3
1 2 3 4 5
0 1 1 0 2
2 4 5
5 3 2
0 1 1 2 3
1 2 3 4 5
0 1 1 2 2
2 4 5

9
8

说明/提示

样例解释

对于第一组数据，历史事件之间的关系如下图：

她可以进行以下的回忆过程：

总用时 $1+1+2+1+4=9$。

数据范围与限制

本题采用捆绑测试，各 Subtask 的限制与分值如下。

特殊性质 A：保证 $p_i=0$ 或 $p_i=i-1$；

特殊性质 B：保证 $p_i=\lfloor\frac i2\rfloor$；

特殊性质 C：保证 $p_i\le1$。

对于所有数据，满足 $1\le T\le5$，$1\le n,m\le10^5$，$1\le k\le10$，$0\le p_i<i$，$0\le r_i,t_i\le10^9$，$1\le x_i\le n$。