AT_scpc2026_div1_d Mobilint Tensor Scheduling (ARIES)

#### 表示言語 / / ザイは Mobilint の SDK を用いて，ARIES 上で実行する AI 推論コードを書こうとしています．ザイはコーディングがあまり得意でない開発者なので，ザイが書いたコードでは木状のグラフしか計算できません． ザイはこのコードで， $ N $ 個のテンソルからなる根付き木状の計算グラフを計算します．木の根は頂点 $ 1 $ です．木の頂点 $ i $ は，サイズが $ w_i $ MiB であるテンソルを表します． 葉が表すテンソルを**入力テンソル**，葉でない頂点が表すテンソルを**結果テンソル**と呼びます．入力テンソルは初期状態ですでにメモリ上に存在します．初期状態でのメモリ使用量は $ M $ MiB 以下です． 頂点 $ i $ が表す結果テンソルを計算するためには， $ i $ のすべての子が表すテンソルが現在メモリ上に存在している必要があります．頂点 $ i $ が表す結果テンソルを計算するときは，まずサイズ $ w_i $ MiB の結果テンソルをメモリ上に確保します．その計算が完了した直後に， $ i $ のすべての子が表すテンソルをメモリから削除します． ある時点でのメモリ使用量を，その時点でメモリ上に存在するすべてのテンソルのサイズの総和と定義します． ザイは計算順序を適切に選ぶことで，根が表すテンソルを計算するときのピークメモリ使用量を最小化したいです．ピークメモリ使用量とは，初期状態および計算過程のすべての時点におけるメモリ使用量の最大値です． 使用するコンピュータのメモリ上限は $ M $ MiB です．計算中のどの時点においても，メモリ使用量は $ M $ MiB 以下でなければなりません． 根が表す結果テンソルを計算するために必要なピークメモリ使用量の最小値を求めてください．

入力は以下の形式で標準入力から与えられる． > $ N $ $ M $ $ w_1 $ $ w_2 $ $ \dots $ $ w_N $ $ p_2 $ $ p_3 $ $ \dots $ $ p_N $ ここで， $ p_i $ は頂点 $ i $ の親を表す．

ピークメモリ使用量が $ M $ MiB 以下となるように根が表す結果テンソルを計算できるならば，可能なピークメモリ使用量の最小値を出力する． そうでなければ，代わりに `OOM` を出力する．

### Sample Explanation 1 初期状態では，メモリ上に存在するテンソルは，葉である頂点 $ 5,6,7,8 $ が表す入力テンソルです．したがって，このときのメモリ使用量は $ 2+4+3+1=10 $ MiB です． 例えば，次の順序で結果テンソルを計算できます． 1. 頂点 $ 4 $ が表す結果テンソルを計算する．このステップ中のメモリ使用量の最大値は $ 10+3=13 $ MiB である． 2. 頂点 $ 3 $ が表す結果テンソルを計算する．このステップ中のメモリ使用量の最大値は $ 9+5=14 $ MiB である． 3. 頂点 $ 2 $ が表す結果テンソルを計算する．このステップ中のメモリ使用量の最大値は $ 10+4=14 $ MiB である． 4. 頂点 $ 1 $ が表す結果テンソルを計算する．このステップ中のメモリ使用量の最大値は $ 9+6=15 $ MiB である． この計算順序におけるピークメモリ使用量は $ 15 $ MiB です．ピークメモリ使用量を $ 14 $ MiB 以下にすることはできないため，答えは $ 15 $ です． ### Constraints - $ 2 \leq N \leq 200\,000 $ - $ M = 16\,384 $ - $ 1 \leq w_i \leq M $ - $ 1 \leq p_i \leq N $ - 与えられるグラフは頂点 $ 1 $ を根とする根付き木である． - 入力される数値はすべて整数