Little F 今天去参加了一个聚会，现在他想组织大家一起玩个游戏！

共有 $N$ 个人参加了游戏（Little F 负责观看）。Little F 准备了 $N$ 枚相同的硬币。游戏开始时，每个人恰好拥有一枚硬币，且每个人都有一个数字 $a_i$，表示他最多能持有的硬币数量。

游戏中共有 $M$ 轮。在每一轮中，Little F 会选择两个人 $A$ 和 $B$（当然，这两个人是不同的），然后这两个人有三种选择： 1. $A$ 给 $B$ 一枚硬币 2. $B$ 给 $A$ 一枚硬币 3. 什么都不做

注意，在任何时候，每个人持有的硬币数量都不能超过他的持有上限 $a_i$。

在这 $N$ 个人中，有 $K$ 个人是 Little F 的朋友。现在 Little F 想知道，在 $M$ 轮游戏结束后，在所有可能的情况下，他的 $K$ 位朋友持有的硬币总数最多是多少。

输入格式

第一行包含一个正整数 $T$，表示测试组数。对于每组测试数据： 第一行包含三个整数 $N, M, K$，分别表示总人数、游戏轮数和 Little F 的朋友数量。 下一行包含 $N$ 个整数，其中第 $i$ 个数 $a_i$ 表示第 $i$ 个人的硬币持有上限。 接下来的 $M$ 行，每行给出两个整数 $(A, B)$，表示这一轮游戏中选中的人是 $A$ 和 $B$。 最后一行包含 $K$ 个数字 $b_1, b_2, \dots, b_k$，表示 Little F 的 $K$ 位朋友。

$1 \le T \le 10, 1 \le N, M, a_i \le 3000, 1 \le K \le N$

输出格式

对于每组测试数据，输出一行一个整数，表示 Little F 的 $K$ 位朋友持有的硬币总数的最大值。

样例

输入样例 1

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

输出样例 1

3
4