AT_scpc2026_div1_d Mobilint Tensor Scheduling (ARIES)

#### 表示言語 / / Zye is writing AI inference code to run on ARIES 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.

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 $ .

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.

### Sample Explanation 1 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 $ 2+4+3+1=10 $ 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 $ 10+3=13 $ MiB. 2. Compute the result tensor represented by node $ 3 $ . The maximum memory usage during this step is $ 9+5=14 $ MiB. 3. Compute the result tensor represented by node $ 2 $ . The maximum memory usage during this step is $ 10+4=14 $ MiB. 4. Compute the result tensor represented by node $ 1 $ . The maximum memory usage during this step is $ 9+6=15 $ MiB. The peak memory usage for this computation order is $ 15 $ MiB. It is impossible to make the peak memory usage at most $ 14 $ MiB, so the answer is $ 15 $ . ### Constraints - $ 2 \leq N \leq 200\,000 $ - $ M = 16\,384 $ - $ 1 \leq w_i \leq M $ - $ 1 \leq p_i \leq N $ - The given graph is a rooted tree with root node $ 1 $ . - All input values are integers.