Skip to content
Sign in

ビリヤード (Billiards)

Unrated
日本語

Language

Contribute a translation
Time limit
1000 ms
Memory limit
1024 MB
Submissions
0
Correct
0
Solved by
0
AC rate
—

Statement

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

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

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

Subtasks

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

Input

入力は以下の形式で与えられる．

\(N\) \(X\)
\(A_1\) \(A_2\) \(\dots\) \(A_N\)
\(P_1\) \(P_2\) \(\dots\) \(P_N\)

Output

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

Examples

Sample input 1
6 7
1 2 4 3 10 100
-1 -1 -1 -1 -1 -1
Sample output 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\) の制約を満たす．

Sample input 2
5 12
1 2 3 5 8
-1 1 2 3 4
Sample output 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\) の制約を満たす．

Sample input 3
8 10
3 1 4 1 5 9 2 6
-1 1 2 -1 4 4 5 7
Sample output 3
7

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

Sample input 4
2 1000000000000000
1 1
2 1
Sample output 4
-1

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

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

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

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

Notes

JOI 2025 · JCIOI · CC BY-SA 4.0

Tags

No tags yet

Source