你是鸽子王国的国王。鸽子王国由 $n$ 个城市和 $n-1$ 条双向道路组成，每条道路连接一对城市。保证任意两个城市之间都可以通过道路相互到达。

每条道路都有颜色（黑色或白色）和长度 $\ell_i$。最初，所有道路都是白色的。然而，你觉得这样太无聊了，于是你决定指派 $m$ 个机器人到 $m$ 个城市，将道路涂成你喜欢的颜色图案。不同的机器人可以被指派到同一个城市。机器人 $i$ 从城市 $p_i$ 出发，经过一些道路（可能为零），然后停止。机器人不能多次经过同一条道路。当机器人经过一条道路时，它会翻转该道路的颜色（如果是白色，则变为黑色；反之亦然）。机器人是独立的，这意味着它们在移动过程中不会相互干扰。我们假设不同的机器人不会同时涂抹任何道路。此外，不同的机器人可以在同一个城市停止。机器人移动的代价定义为它所经过的所有道路的长度之和。

作为鸽子王国的国王，你希望最小化所有机器人移动的总代价。如果无法用 $m$ 个机器人将道路涂成所需的图案，请输出 $-1$。

输入格式

第一行包含一个整数 $t$，表示测试用例的数量 ($1 \le t \le 5000$)。接下来是各测试用例。

每个测试用例的第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 5000$，$1 \le m \le 5000$)，分别表示城市数量和机器人数量。

接下来的 $n-1$ 行，每行包含四个整数 $u_i, v_i, \ell_i, c_i$ ($1 \le u_i < v_i \le n$；$1 \le \ell_i \le 10$；$c_i = 0$ 或 $c_i = 1$)，表示一条连接城市 $u_i$ 和 $v_i$、长度为 $\ell_i$ 的道路。如果 $c_i = 0$，则在目标图案中应将其涂为白色；否则，应将其涂为黑色。保证任意两个城市之间都可以通过给定的道路相互到达。

最后一行包含 $m$ 个整数 $p_j$ ($1 \le p_j \le n$)，表示每个机器人的起始城市。

保证所有测试用例中 $n$ 的总和不超过 $5000$，$m$ 的总和不超过 $5000$。

输出格式

对于每个测试用例，输出一行，包含一个整数：将所有道路涂成所需图案的最小总代价。如果无法做到，则输出 $-1$。

样例

输入 1

5
3 2
1 2 1 1
2 3 2 1
1 3
4 2
1 2 3 1
2 3 1 0
3 4 4 1
1 2
5 4
1 2 3 0
2 3 1 1
3 4 2 0
4 5 2 1
1 1 1 1
5 2
1 2 2 1
1 3 3 0
1 5 2 1
3 4 1 1
1 2
10 5
1 2 10 1
2 3 3 1
3 4 4 0
4 5 4 1
5 6 2 1
2 7 8 0
2 8 9 1
4 9 1 0
1 10 4 0
10 10 2 1 8

输出 1

3
9
21
-1
42