Description

Wile 独自生活在沙漠中，他通过建造复杂的连锁反应机器来自娱自乐。每台机器由 $\mathbf{N}$ 个模块组成，编号为 $1, 2, \ldots, \mathbf{N}$。每个模块会指向一个编号比它小的模块，如果没有可指向的模块，则指向虚空。

没有被任何其他模块指向的模块称为启动器。Wile 可以手动触发启动器。当一个模块被触发时，它会触发它所指向的模块（如果有的话），后者可能继续触发第三个模块（如果它指向某个模块），依此类推，直到链条到达虚空或已经触发过的模块为止。这被称为连锁反应。

每个 $\mathbf{N}$ 个模块都有一个乐趣值 $\mathbf{F}_i$。Wile 从一次连锁反应中获得的乐趣是该连锁反应中所有被触发模块的乐趣值的最大值。Wile 将按某种顺序依次触发每个启动器模块一次。整个过程中 Wile 获得的总乐趣是每次连锁反应所获乐趣的总和。

例如，假设 Wile 有 4 个模块，乐趣值分别为 $\mathbf{F}_1 = 60$、$\mathbf{F}_2 = 20$、$\mathbf{F}_3 = 40$ 和 $\mathbf{F}_4 = 50$，模块 1 指向虚空，模块 2 和 3 指向模块 1，模块 4 指向模块 2。此时有两个启动器（3 和 4），Wile 需要按某种顺序触发它们。

如上图所示，如果 Wile 先手动触发模块 4，模块 4、2 和 1 会在同一次连锁反应中被触发，乐趣值为 $\max(50, 20, 60) = 60$。接着，当 Wile 触发模块 3 时，模块 3 会单独被触发（模块 1 无法再次触发），乐趣值为 40，整个过程的总乐趣为 $60 + 40 = 100$。

然而，如果 Wile 先手动触发模块 3，模块 3 和 1 会在同一次连锁反应中被触发，乐趣值为 $\max(40, 60) = 60$。接着，当 Wile 触发模块 4 时，模块 4 和 2 会在同一次连锁反应中被触发，乐趣值为 $\max(50, 20) = 50$，整个过程的总乐趣为 $60 + 50 = 110$。

给定模块的乐趣值和指向关系，计算 Wile 在最优触发顺序下能获得的最大总乐趣。

Input Format

输入的第一行给出测试用例的数量 $\mathbf{T}$。随后是 $\mathbf{T}$ 个测试用例，每个测试用例由 3 行描述。每个测试用例的第一行包含一个整数 $\mathbf{N}$，表示 Wile 拥有的模块数量。第二行包含 $\mathbf{N}$ 个整数 $\mathbf{F}_1, \mathbf{F}_2, \ldots, \mathbf{F}_\mathbf{N}$，其中 $\mathbf{F}_i$ 是第 $i$ 个模块的乐趣值。第三行包含 $\mathbf{N}$ 个整数 $\mathbf{P}_1, \mathbf{P}_2, \ldots \mathbf{P}_\mathbf{N}$。如果 $\mathbf{P}_i = 0$，表示模块 $i$ 指向虚空；否则，模块 $i$ 指向模块 $\mathbf{P}_i$。

Output Format

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是 Wile 在最优触发顺序下能获得的最大总乐趣。

3
4
60 20 40 50
0 1 1 2
5
3 2 1 4 5
0 1 1 1 0
8
100 100 100 90 80 100 90 100
0 1 2 1 2 3 1 3

Case #1: 110
Case #2: 14
Case #3: 490

Hint

样例解释

样例 #1 是题目描述中解释的案例。

在样例 #2 中，有 $4$ 个启动器（模块 $2$ 到 $5$），因此有 $4$ 次连锁反应。按顺序 $3, 5, 4, 2$ 触发它们，得到的连锁反应乐趣值分别为 $3, 5, 4, 2$，总乐趣为 $14$。注意我们是在对输入中的四个最大乐趣值求和，因此无法获得更大的值。

在样例 #3 中，$5$ 个启动器的最优触发顺序是 $4, 5, 7, 6, 8$。

限制条件

• $1 \leq \mathbf{T} \leq 100$。
• $1 \leq \mathbf{F}_i \leq 10^9$。
• $0 \leq \mathbf{P}_i \leq i - 1$，对所有 $i$ 成立。

测试集 1（10 分，可见评测结果）

• 时间限制：5 秒。
• $1 \leq \mathbf{N} \leq 10$。

测试集 2（12 分，可见评测结果）

• 时间限制：5 秒。
• $1 \leq \mathbf{N} \leq 1000$。

测试集 3（5 分，隐藏评测结果）

• 时间限制：10 秒。
• $1 \leq \mathbf{N} \leq 100000$。

翻译由 DeepSeek V3 完成