题目背景

「浅村同学对于我……」
「理解得太深了。」
——绫濑沙季

题目描述

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

有 $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
13 13 3
0 1 2 3 3 4 4 5 5 6 7 8 9
1 3 5 7 7 10 10 10 10 13 13 13 13
0 1 1 1 1 2 2 2 2 2 2 2 2
1 2 3 4 5 6 7 8 9 10 11 12 13

22

提示

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