問題文

ビ太郎はビリヤードで遊んでいる． 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 がすでに落とされている必要がある．

ビ太郎が持つ集中力と各ボールの情報が与えられたとき，ビ太郎がボールを穴に落とすことができるか判定し，ボールを落とすことができる場合は落とせるボールの番号の最大値を求めるプログラムを作成せよ．

制約

• 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)．
• 入力される値はすべて整数である．

小課題

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 点) 追加の制約はない．

入力例 1

6 7
1 2 4 3 10 100
-1 -1 -1 -1 -1 -1

出力例 1

4

はじめ，ビ太郎の集中力は 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 の制約を満たす．

入力例 2

5 12
1 2 3 5 8
-1 1 2 3 4

出力例 2

4

はじめ，ビ太郎の集中力は 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 の制約を満たす．

入力例 3

8 10
3 1 4 1 5 9 2 6
-1 1 2 -1 4 4 5 7

出力例 3

7

この入力例は小課題 3,4,5,6 の制約を満たす．

入力例 4

2 1000000000000000
1 1
2 1

出力例 4

-1

P_1 = 2 なので，ボール 1 を落とすためには，ボール 2 がすでに落とされている必要がある．逆に， P_2 = 1 なので，ボール 2 を落とすためには，ボール 1 がすでに落とされている必要がある．このことから，ビ太郎は 1 個もボールを落とすことができない．よって， -1 を出力する．

この入力例は小課題 5,6 の制約を満たす．

入力例 5

9 2468024680
123456789 234567891 345678912 456789123 567891234 678912345 789123456 891234567 912345678
6 5 4 -1 3 2 1 9 8

出力例 5

6

この入力例は小課題 5,6 の制約を満たす．