AT_joi2025_yo2_b ビリヤード (Billiards)

ビ太郎はビリヤードで遊んでいる． JOI 国のビリヤードは台上に並べられた $ N $ 個のボール $ 1,2,...,N $ を用いる遊びであり，台にはボールを落とすための穴が設けられている． 一度穴に落ちたボールは台上には戻さず，そのボールを再び落とすことはできない．ビ太郎の目的は，なるべく大きい番号の書かれたボールを穴に落とすことである． ボールを落とすのは集中を必要とする作業である． はじめ，ビ太郎の **集中力** は $ X $ であり，ボール $ i $ ( $ 1 \leqq i \leqq N $ ) を落とすと集中力が $ A_i $ 減少する．集中力が $ A_i $ 未満であるとき，ボール $ i $ を落とすことはできない． また，このビリヤードではボールを落とす順番に関するルールが存在する．具体的には， $ P_i = -1 $ ( $ 1 \leqq i \leqq N $ ) のとき，ボール $ i $ はいつでも落とすことができ， $ P_i \neq -1 $ のとき，ボール $ i $ を落とすためには，ボール $ P_i $ がすでに落とされている必要がある． ビ太郎が持つ集中力と各ボールの情報が与えられたとき，ビ太郎がボールを穴に落とすことができるか判定し，ボールを落とすことができる場合は落とせるボールの番号の最大値を求めるプログラムを作成せよ．

入力は以下の形式で与えられる． > $ N $ $ X $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $ $ P_1 $ $ P_2 $ $ \dots $ $ P_N $

ビ太郎が穴に落とすことのできるボールの番号の最大値を $ 1 $ 行に出力せよ． ただし，ビ太郎が $ 1 $ 個もボールを落とすことができない場合は代わりに `-1` と出力せよ．

### 小課題 1. ( $ 6 $ 点) $ N \leqq 1000 $ ， $ P_i = -1 $ ( $ 1 \leqq i \leqq N $ )． 2. ( $ 9 $ 点) $ N \leqq 1000 $ ， $ P_1 = -1 $ ， $ P_i = i-1 $ ( $ 2 \leqq i \leqq N $ )． 3. ( $ 16 $ 点) $ N \leqq 1000 $ ， $ P_i < i $ ( $ 1 \leqq i \leqq N $ )． 4. ( $ 20 $ 点) $ P_i < i $ ( $ 1 \leqq i \leqq N $ )． 5. ( $ 19 $ 点) $ N \leqq 1000 $ ． 6. ( $ 30 $ 点) 追加の制約はない． ### Sample Explanation 1 はじめ，ビ太郎の集中力は $ 7 $ である． すべての $ i $ ( $ 1 \leqq i \leqq N $ ) について $ P_i = -1 $ なので，ビ太郎は集中力が足りる限り，すべでのボールをいつでも穴に落とすことができる． 例えば，以下のようにすると，ビ太郎はボール $ 4 $ を落とすことができる． - まず，ボール $ 3 $ を穴に落とす．ビ太郎の集中力が $ 4 $ 減少し，残りの集中力は $ 3 $ となる． - 次に，ボール $ 4 $ を穴に落とす．ビ太郎の集中力が $ 3 $ 減少し，残りの集中力は $ 0 $ となる． また，ビ太郎がボール $ 5,6 $ を穴に落とすことはできない．よって，ビ太郎が穴に落とすことのできるボールの番号の最大値は $ 4 $ である． この入力例は小課題 $ 1,3,4,5,6 $ の制約を満たす． ### Sample Explanation 2 はじめ，ビ太郎の集中力は $ 12 $ である． 例えば，以下のようにすると，ビ太郎はボール $ 4 $ を落とすことができる． - まず，ボール $ 1 $ を穴に落とす． ( $ P_1 = -1 $ なので，ボール $ 1 $ はいつでも落とすことができる．) - ビ太郎の集中力が $ 1 $ 減少し，残りの集中力は $ 11 $ となる． - 次に，ボール $ 2 $ を穴に落とす． ( $ P_2 = 1 $ でありボール $ 1 $ はすでに落とされているので，ボール $ 2 $ を落とすことができる．) - ビ太郎の集中力が $ 2 $ 減少し，残りの集中力は $ 9 $ となる． - 次に，ボール $ 3 $ を穴に落とす． ( $ P_3 = 2 $ でありボール $ 2 $ はすでに落とされているので，ボール $ 3 $ を落とすことができる．) - ビ太郎の集中力が $ 3 $ 減少し，残りの集中力は $ 6 $ となる． - 次に，ボール $ 4 $ を穴に落とす． ( $ P_4 = 3 $ でありボール $ 3 $ はすでに落とされているので，ボール $ 4 $ を落とすことができる．) - ビ太郎の集中力が $ 5 $ 減少し，残りの集中力は $ 1 $ となる． また，ビ太郎がボール $ 5 $ を穴に落とすことはできない．よって，ビ太郎が穴に落とすことのできるボールの番号の最大値は $ 4 $ である． この入力例は小課題 $ 2,3,4,5,6 $ の制約を満たす． ### Sample Explanation 3 この入力例は小課題 $ 3,4,5,6 $ の制約を満たす． ### Sample Explanation 4 $ P_1 = 2 $ なので，ボール $ 1 $ を落とすためには，ボール $ 2 $ がすでに落とされている必要がある．逆に， $ P_2 = 1 $ なので，ボール $ 2 $ を落とすためには，ボール $ 1 $ がすでに落とされている必要がある．このことから，ビ太郎は $ 1 $ 個もボールを落とすことができない．よって， `-1` を出力する． この入力例は小課題 $ 5,6 $ の制約を満たす． ### Sample Explanation 5 この入力例は小課題 $ 5,6 $ の制約を満たす． ### Constraints - $ 1 \leqq N \leqq 200\,000 $ ． - $ 1 \leqq X \leqq 10^{15} $ ． - $ 1 \leqq A_i \leqq 10^9 $ ( $ 1 \leqq i \leqq N $ )． - $ 1 \leqq P_i \leqq N $ または $ P_i = -1 $ ( $ 1 \leqq i \leqq N $ )． - $ P_i \neq i $ ( $ 1 \leqq i \leqq N $ )． - 入力される値はすべて整数である．