ビリヤード (Billiards)

시간 제한1초메모리 제한2048 MB

요약
집중력 예산과 각 공의 비용, 그리고 선행 조건이 주어질 때, 어떤 순서로든 넣을 수 있는 가장 큰 번호의 공을 구한다.
난이도

보통10점 중 6점

유형
위상 정렬, 그리디, 힙, 그래프
정답자
아직 제출이 없습니다

문제

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

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

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

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

입력

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

N X
A1 A2 … AN
P1 P2 … PN

출력

ビ太郎が穴に落とすことのできるボールの番号の最大値を 1 行に出力せよ．

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

제한

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

예제5

  1. 예제 1

    입력
    6 7
1 2 4 3 10 100
-1 -1 -1 -1 -1 -1
    예상 출력
    4

  2. 예제 2

    입력
    5 12
1 2 3 5 8
-1 1 2 3 4
    예상 출력
    4

  3. 예제 3

    입력
    8 10
3 1 4 1 5 9 2 6
-1 1 2 -1 4 4 5 7
    예상 출력
    7

  4. 예제 4

    입력
    2 1000000000000000
1 1
2 1
    예상 출력
    -1

  5. 예제 5

    입력
    9 2468024680
123456789 234567891 345678912 456789123 567891234 678912345 789123456 891234567 912345678
6 5 4 -1 3 2 1 9 8
    예상 출력
    6