Description

你负责管理一个铁路运输网络。该网络由 $\mathbf{N}$ 个车站组成。每个车站 $i$ 需要向另一个车站 $\mathbf{D}_i$ 运输货物。车站 $i$ 将发送恰好一趟列车，该列车包含恰好 $\mathbf{C}_i$ 节车厢。

你提前获得了所有运输信息，因此计划通过重复使用车厢来节省资源。如果车站 $i$ 向车站 $\mathbf{D}_i$ 发送了 $n$ 节车厢，那么车站 $\mathbf{D}_i$ 可以将这些车厢加入自己的资源库以供后续使用（前提是这些车厢尚未被使用过）。

具体来说，你需要为每个车站分配初始车厢数量（某些车站可能分配 0 节），并确定运输顺序，使得当车站 $i$ 需要进行运输时，其初始分配的车厢数量加上之前到达该站的车厢数量至少等于其运输需求 $\mathbf{C}_i$。注意：即使车站 $i$ 当前拥有的车厢数量多于 $\mathbf{C}_i$，每次运输也只能发送恰好 $\mathbf{C}_i$ 节车厢。

例如，假设车站 1 向车站 4 发送了 3 节车厢。如果车站 4 需要 2 节车厢，它可以重复使用从车站 1 接收的 2 节车厢。如果车站 4 需要发送 5 节车厢，它可以重复使用从车站 1 接收的 3 节车厢，并额外使用自己初始分配的 2 节。需要注意的是，当车站 4 只需要发送 2 节车厢时，它不能发送从车站 1 接收的全部 3 节车厢。

给定运输信息，问：在所有可能的运输顺序中，车站初始分配的车厢总数的最小值是多少？

Input Format

输入的第一行给出测试用例的数量 $\mathbf{T}$。随后是 $\mathbf{T}$ 个测试用例。每个测试用例包含 3 行：第一行是一个整数 $\mathbf{N}$，表示车站数量；第二行包含 $\mathbf{N}$ 个整数 $\mathbf{D}_1, \mathbf{D}_2, \ldots, \mathbf{D}_\mathbf{N}$；第三行包含 $\mathbf{N}$ 个整数 $\mathbf{C}_1, \mathbf{C}_2, \ldots, \mathbf{C}_\mathbf{N}$。这表示车站 $i$ 需要向车站 $\mathbf{D}_i$ 发送恰好 $\mathbf{C}_i$ 节车厢。

Output Format

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是满足所有运输需求所需的最少初始车厢总数。

3
4
2 3 4 3
4 3 2 1
4
2 3 4 1
1 3 1 3
7
3 5 2 5 3 7 6
3 4 6 3 5 1 2

Case #1: 4
Case #2: 5
Case #3: 10

Hint

样例解释

在样例 #1 中，最优方案是按照车站编号递增的顺序进行运输。这需要为车站 1 初始分配 4 节车厢。之后每个车站都能从接收的车厢中获得足够的资源，因此初始车厢总数为 4。由于没有车厢到达车站 1，它必须初始拥有全部 4 节车厢，因此这也是可能的最小值。

在样例 #2 中，一种最优方案是为车站 3 分配 1 节车厢，为车站 2 和 4 各分配 2 节车厢，总计 5 节。然后可以先执行运输 $3 \rightarrow 4$，这将为车站 4 增加 1 节车厢。此时车站 4 拥有 3 节车厢，足以完成运输 $4 \rightarrow 1$。车站 1 现在有 3 节车厢，可以完成运输 $1 \rightarrow 2$（只发送 1 节），使车站 2 的车厢总数达到 3 节，足以完成最后的运输 $2 \rightarrow 3$。注意运输 $1 \rightarrow 2$ 不能额外发送更多车厢，即使这对后续运输有帮助。存在其他使用 5 节初始车厢的方案，但无法使用更少的初始车厢完成所有运输。

在样例 #3 中，一种最优方案是为车站 1 和 4 各分配 3 节车厢，为车站 5 和 7 各分配 2 节车厢。

数据范围

• $1 \leq \mathbf{T} \leq 100$。
• 对所有 $i$，$1 \leq \mathbf{D}_i \leq \mathbf{N}$。
• 对所有 $i$，$\mathbf{D}_i \neq i$。
• 对所有 $i$，$1 \leq \mathbf{C}_i \leq 10^9$。

测试集 1（9 分，可见判定）

• $2 \leq \mathbf{N} \leq 8$。

测试集 2（20 分，可见判定）

• $2 \leq \mathbf{N} \leq 10^5$。

翻译由 DeepSeek V3 完成