第24回日本情報オリンピック　二次予選

2024年12月10日
情報オリンピック日本委員会

問題文

ビ太郎はビリヤードで遊んでいる． JOI 国のビリヤードは台上に並べられた N 個のボール 1,2,...,N を用いる遊びであり，台にはボールを落とすための穴が設けられている． 一度穴に落ちたボールは台上には戻さず，そのボールを再び落とすことはできない．ビ太郎の目的は，なるべく大きい番号の書かれたボールを穴に落とすことである．

ボールを落とすのは集中を必要とする作業である． はじめ，ビ太郎の 集中力 は X であり，ボール i (1 ≦ i ≦ N) を落とすと集中力が A_i 減少する．集中力が A_i 未満であるとき，ボール i を落とすことはできない．

また，このビリヤードではボールを落とす順番に関するルールが存在する．具体的には， P_i = -1 (1 ≦ i ≦ N) のとき，ボール i はいつでも落とすことができ， P_i ≠ -1 のとき，ボール i を落とすためには，ボール P_i がすでに落とされている必要がある．

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

制約

• 1 ≦ N ≦ 200 000．
• 1 ≦ X ≦ 10¹⁵．
• 1 ≦ A_i ≦ 10⁹ (1 ≦ i ≦ N)．
• 1 ≦ P_i ≦ N または P_i = -1 (1 ≦ i ≦ N)．
• P_i ≠ i (1 ≦ i ≦ N)．
• 入力される値はすべて整数である．

小課題

1. (6 点) N ≦ 1000， P_i = -1 (1 ≦ i ≦ N)．
2. (9 点) N ≦ 1000， P₁ = -1， P_i = i-1 (2 ≦ i ≦ N)．
3. (16 点) N ≦ 1000， P_i < i (1 ≦ i ≦ N)．
4. (20 点) P_i < i (1 ≦ i ≦ N)．
5. (19 点) N ≦ 1000．
6. (30 点) 追加の制約はない．

入力

入力は以下の形式で与えられる．
N X
A₁ A₂ … A_N
P₁ P₂ … P_N

出力

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

入出力例

入力例 1
6 7
1 2 4 3 10 100
-1 -1 -1 -1 -1 -1

出力例 1
4

はじめ，ビ太郎の集中力は 7 である．
すべての i (1 ≦ i ≦ 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 減少し，残りの集中力は 11 となる．
• 次に，ボール 2 を穴に落とす． ( P₂ = 1 でありボール 1 はすでに落とされているので，ボール 2 を落とすことができる．)
  • ビ太郎の集中力が 2 減少し，残りの集中力は 9 となる．
• 次に，ボール 3 を穴に落とす． ( P₃ = 2 でありボール 2 はすでに落とされているので，ボール 3 を落とすことができる．)
  • ビ太郎の集中力が 3 減少し，残りの集中力は 6 となる．
• 次に，ボール 4 を穴に落とす． ( P₄ = 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₁ = 2 なので，ボール 1 を落とすためには，ボール 2 がすでに落とされている必要がある．逆に， P₂ = 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 の制約を満たす．