AT_scpc2026_div3_b.Mobilint Tensor Scheduling (REGULUS)

Zye is writing AI inference code to run on REGULUS using Mobilint's SDK. Since Zye is a developer who is not very good at coding, the code he writes can compute only tree-shaped graphs.

Using this code, Zye wants to compute a rooted tree-shaped computation graph consisting of $N$ tensors. The root of the tree is node $1$. Node $i$ of the tree represents a tensor of size $w_i$ MiB.

A tensor represented by a leaf node is called an input tensor, and a tensor represented by a non-leaf node is called a result tensor. Input tensors already exist in memory in the initial state. The memory usage in the initial state is at most $M$ MiB.

To compute the result tensor represented by node $i$, all tensors represented by the children of $i$ must currently exist in memory. When computing the result tensor represented by node $i$, first the result tensor of size $w_i$ MiB is allocated in memory. After the computation is finished, all tensors represented by the children of $i$ are removed from memory.

The memory usage at a certain moment is defined as the sum of the sizes of all tensors that exist in memory at that moment.

Zye wants to choose the computation order so that the peak memory usage while computing the tensor represented by the root node is minimized. The peak memory usage is the maximum memory usage over the initial state and all moments during the computation.

The memory limit of the computer is $M$ MiB. During the computation, the memory usage must always be at most $M$ MiB.

Find the minimum peak memory usage needed to compute the result tensor represented by the root node.

Zye 正在为 REGULUS 平台使用 Mobilint 的 SDK 编写 AI 推理代码。由于 Zye 是一位编程能力不太强的开发者，他所编写的代码仅能处理树状结构的计算图。

利用该代码，Zye 希望计算一个由 $N$ 个张量构成的、以节点 $1$ 为根的树状计算图。树中节点 $i$ 表示一个大小为 $w_i$ MiB 的张量。

由叶节点表示的张量称为输入张量，由非叶节点表示的张量称为结果张量。初始状态下，所有输入张量已存在于内存中，此时的内存占用至多为 $M$ MiB。

为计算由节点 $i$ 表示的结果张量，其所有子节点所表示的张量必须当前均存在于内存中。在计算由节点 $i$ 表示的结果张量时，首先需在内存中分配一个大小为 $w_i$ MiB 的结果张量；计算完成后，所有由 $i$ 的子节点所表示的张量将从内存中被移除。

某一时刻的内存占用定义为该时刻内存中所有现存张量的大小之和。

Zye 希望选择一种计算顺序，使得在计算根节点所表示的张量过程中，峰值内存占用最小化。此处峰值内存占用指初始状态及整个计算过程中所有时刻内存占用的最大值。

该计算机的内存限制为 $M$ MiB。在整个计算过程中，内存占用必须始终不超过 $M$ MiB。

求计算根节点所表示的结果张量所需的最小峰值内存占用。

The input is given from Standard Input in the following format:

$N$ $M$
$w_1$ $w_2$ $\dots$ $w_N$
$p_2$ $p_3$ $\dots$ $p_N$

Here, $p_i$ denotes the parent of node $i$.

输入从标准输入中按以下格式给出：

$N$ $M$
$w_1$ $w_2$ $\dots$ $w_N$
$p_2$ $p_3$ $\dots$ $p_N$

其中，$p_i$ 表示节点 $i$ 的父节点。

If it is possible to compute the result tensor represented by the root node so that the peak memory usage is at most $M$ MiB, output the minimum possible peak memory usage.

Otherwise, output OOM instead.

如果可以计算出根节点所表示的结果张量，且峰值内存使用量不超过 $M$ MiB，则输出可能的最小峰值内存使用量。
否则，输出 OOM。

表示言語

/ /

Sample 1 Explanation:
In the initial state, the tensors that exist in memory are the input tensors represented by leaf nodes $5,6,7,8$. Therefore, the memory usage is $1+1+1+1=4$ MiB.

For example, the result tensors can be computed in the following order.

1. Compute the result tensor represented by node $4$. The maximum memory usage during this step is $4+1=5$ MiB.
2. Compute the result tensor represented by node $3$. The maximum memory usage during this step is $4+1=5$ MiB.
3. Compute the result tensor represented by node $2$. The maximum memory usage during this step is $3+1=4$ MiB.
4. Compute the result tensor represented by node $1$. The maximum memory usage during this step is $2+1=3$ MiB.

The peak memory usage for this computation order is $5$ MiB. It is impossible to make the peak memory usage at most $4$ MiB, so the answer is $5$.

Constraints

• $2 \leq N \leq 5\,000$
• $M = 8\,192$
• $w_i = 1$
• $1 \leq p_i \leq N$
• The given graph is a rooted tree with root node $1$.
• All input values are integers.

表示语言

/ /

样例 1 解释：
初始状态下，内存中已存在的张量是叶节点 $5,6,7,8$ 所表示的输入张量。因此，此时内存占用为 $1+1+1+1=4$ MiB。

例如，结果张量可按如下顺序计算：

1. 计算节点 $4$ 所表示的结果张量。该步骤中的最大内存占用为 $4+1=5$ MiB。
2. 计算节点 $3$ 所表示的结果张量。该步骤中的最大内存占用为 $4+1=5$ MiB。
3. 计算节点 $2$ 所表示的结果张量。该步骤中的最大内存占用为 $3+1=4$ MiB。
4. 计算节点 $1$ 所表示的结果张量。该步骤中的最大内存占用为 $2+1=3$ MiB。

该计算顺序下的峰值内存占用为 $5$ MiB。无法使峰值内存占用不超过 $4$ MiB，因此答案为 $5$。

约束条件

• $2 \leq N \leq 5\,000$
• $M = 8\,192$
• $w_i = 1$
• $1 \leq p_i \leq N$
• 给定图是一棵以节点 $1$ 为根的有根树。
• 所有输入值均为整数。