Hanaa 和 Sherine 正在玩一个名为 Willow 的游戏，游戏在一个包含 $N$ 个城市的棋盘上进行。第 $i$ 个城市包含 $C_i$ 枚硬币，城市之间有 $N-1$ 条双向道路相连，且所有城市均可互相到达。游戏规则如下：

首先，Hanaa 选择一个城市作为她的起始位置，然后 Sherine 选择一个城市（可以是 Hanaa 选择的同一个城市）作为她的起始位置。之后，两人轮流进行游戏，Hanaa 先手。

在玩家的回合中，该玩家必须拿走她当前所在城市的所有硬币（如果该城市有硬币的话；如果城市初始没有硬币，或者之前已经有玩家在该城市进行过回合，则可能没有硬币）。然后，如果可能的话，玩家必须沿道路移动到相邻的城市。移动可能无法进行，因为每条道路最多只能使用一次。这意味着一旦一名玩家使用了一条道路，之后任何玩家都不得再次使用该道路。当 Hanaa 和 Sherine 都无法移动时，游戏结束。

游戏结束后，每位玩家的得分等于她拥有的硬币数量减去对手拥有的硬币数量。如果对手拥有的硬币更多，则该玩家的得分为负。两位玩家都试图最大化自己的得分。假设她们都采取最优策略来最大化自己的得分，Hanaa 能获得的最高得分是多少？

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含一个整数 $N$，表示棋盘上的城市数量。接下来的 $N$ 行，第 $i$ 行包含一个整数 $C_i$，表示第 $i$ 个城市中的硬币数量。

最后有 $N-1$ 行，第 $i$ 行（$i$ 从 1 开始）包含一个整数 $j$（$i < j \le N$），表示城市 $i$ 和城市 $j$ 之间有一条道路。保证所有城市在游戏开始时均可互相到达。

输出格式

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 是用例编号（从 1 开始），$y$ 是 Hanaa 能获得的最高得分。

数据范围

$1 \le T \le 50$ $0 \le C_i \le 10000$

子任务 1

$2 \le N \le 80$

子任务 2

$2 \le N \le 500$

样例

样例输入 1

3
3
1000
200
1000
2
3
8
8
0
8
0
0
0
0
10
2
5
4
5
6
7
8
10
150
200
0
5000
0
100
0
0
0
10000
10
3
8
5
8
7
8
9
10

样例输出 1

Case #1: 200
Case #2: -2
Case #3: 5100