2157 - ビリヤード (Billiards)

時間制限 1 秒 / メモリ制限 1024 MB / 得点 100 / Writer syoribu / x 1 / 統計 /

TLE
1sec
MLE
1024MB
得点
100

問題文

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

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

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

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

制約

  • 1 ≦ N ≦ 200 000．
  • 1 ≦ X ≦ 1015．
  • 1 ≦ Ai ≦ 109 (1 ≦ i ≦ N)．
  • 1 ≦ Pi ≦ N または Pi = -1 (1 ≦ i ≦ N)．
  • Pi ≠ i (1 ≦ i ≦ N)．
  • 入力される値はすべて整数である．

小課題

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

入力

入力は以下の形式で与えられる．
N X
A1 A2 … AN
P1 P2 … PN

出力

ビ太郎が穴に落とすことのできるボールの番号の最大値を 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) について Pi = -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 を穴に落とす． ( P1 = -1 なので，ボール 1 はいつでも落とすことができる．)
    • ビ太郎の集中力が 1 減少し，残りの集中力は 11 となる．
  • 次に，ボール 2 を穴に落とす． ( P2 = 1 でありボール 1 はすでに落とされているので，ボール 2 を落とすことができる．)
    • ビ太郎の集中力が 2 減少し，残りの集中力は 9 となる．
  • 次に，ボール 3 を穴に落とす． ( P3 = 2 でありボール 2 はすでに落とされているので，ボール 3 を落とすことができる．)
    • ビ太郎の集中力が 3 減少し，残りの集中力は 6 となる．
  • 次に，ボール 4 を穴に落とす． ( P4 = 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

P1 = 2 なので，ボール 1 を落とすためには，ボール 2 がすでに落とされている必要がある．逆に， P2 = 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 の制約を満たす．