레이팅 미적용ビ太郎はビリヤードで遊んでいる. JOI 国のビリヤードは台上に並べられた N 個のボール 1,2,...,N を用いる遊びであり,台にはボールを落とすための穴が設けられている. 一度穴に落ちたボールは台上には戻さず,そのボールを再び落とすことはできない.ビ太郎の目的は,なるべく大きい番号の書かれたボールを穴に落とすことである.
ボールを落とすのは集中を必要とする作業である. はじめ,ビ太郎の 集中力 は X であり,ボール i ( \(1 \le i \le N\) ) を落とすと集中力が A i 減少する.集中力が A i 未満であるとき,ボール i を落とすことはできない.
また,このビリヤードではボールを落とす順番に関するルールが存在する.具体的には, P i = -1 ( \(1 \le i \le N\) ) のとき,ボール i はいつでも落とすことができ, P i ≠ -1 のとき,ボール i を落とすためには,ボール P i がすでに落とされている必要がある.
ビ太郎が持つ集中力と各ボールの情報が与えられたとき,ビ太郎がボールを穴に落とすことができるか判定し,ボールを落とすことができる場合は落とせるボールの番号の最大値を求めるプログラムを作成せよ.
1 ≦ N ≦ 200 000 .
1 ≦ X ≦ 10 15 .
1 ≦ A i ≦ 10 9 ( \(1 \le i \le N\) ).
1 ≦ P i ≦ N または P i = -1 ( \(1 \le i \le N\) ).
P i ≠ i ( \(1 \le i \le N\) ).
入力される値はすべて整数である.
( 6 点) \(N \le 1000\) , P i = -1 ( \(1 \le i \le N\) ).
( 9 点) \(N \le 1000\) , P 1 = -1 , P i = i-1 ( \(2 \le i \le N\) ).
( 16 点) \(N \le 1000\) , P i < i ( \(1 \le i \le N\) ).
( 20 点) P i < i ( \(1 \le i \le N\) ).
( 19 点) \(N \le 1000\) .
( 30 点) 追加の制約はない.
入力は以下の形式で与えられる.
N X
A 1 A 2 ... A N
P 1 P 2 ... P N
ビ太郎が穴に落とすことのできるボールの番号の最大値を 1 行に出力せよ.
ただし,ビ太郎が 1 個もボールを落とすことができない場合は代わりに -1 と出力せよ.
6 7
1 2 4 3 10 100
-1 -1 -1 -1 -1 -1
4
5 12
1 2 3 5 8
-1 1 2 3 4
4
8 10
3 1 4 1 5 9 2 6
-1 1 2 -1 4 4 5 7
7
2 1000000000000000
1 1
2 1
-1
9 2468024680
123456789 234567891 345678912 456789123 567891234 678912345 789123456 891234567 912345678
6 5 4 -1 3 2 1 9 8
6