페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8229
서브태스크

당구장 1초 1024MB

문제

정올이는 당구장에서 놀고 있다. 당구장은 테이블 위에 놓인 N개의 공 1, 2, \cdots, N을 사용하여 하는 게임이다. 테이블에는 공을 떨어뜨릴 수 있는 구멍이 있다. 한 번 구멍에 떨어진 공은 테이블 위로 돌아오지 않으며, 그 공을 다시 떨어뜨릴 수는 없다. 정올이의 목표는 가능한 한 큰 번호가 적힌 공을 구멍에 떨어뜨리는 것이다.

공을 떨어뜨리는 것은 집중력을 요구하는 작업이다. 처음에 정올이의 집중력은 X이며, 공 i (1 ≦ i ≦ N)를 떨어뜨리면 집중력은 A_i만큼 감소한다. 집중력이 A_i 미만일 경우, 공 i를 떨어뜨릴 수 없다.

또한 이 당구장에는 공을 떨어뜨리는 순서에 관한 규칙이 있다. 구체적으로, P_i = -1 (1 ≦ i ≦ N)일 때, 공 i는 언제든지 떨어뜨릴 수 있으며, P_i ≠ -1일 때, 공 i를 떨어뜨리기 위해서는 공 P_i가 이미 떨어져 있어야 한다.

정올이가 가진 집중력과 각 공에 대한 정보가 주어졌을 때, 정올이가 공을 구멍에 떨어뜨릴 수 있는지 판단하고, 공을 떨어뜨릴 수 있다면 떨어뜨릴 수 있는 공의 번호 중 최대값을 구하는 프로그램을 작성하시오.


입력

입력은 다음과 같은 형식으로 주어진다.

N X

A_1\ A_2\ \cdots\ A_N

P_1\ P_2\ \cdots\ P_N

[제약 조건]

  • 1 \le N \le 200,000

  • 1 \le X \le 10^{15}

  • 1 \le A_i \le 10^9 (1 \le i \le N)

  • 1 \le P_i \le N 또는 P_i=-1 (1 \le i \le N)

  • P_i ≠ i (1 \le i \le N)

  • 모든 입력은 정수이다.


출력

정올이가 구멍에 떨어뜨릴 수 있는 공의 번호 중 최대값을 한 줄로 출력하시오.

단, 정올이가 한 개의 공도 떨어뜨릴 수 없는 경우에는 대신 -1을 출력하시오.


부분문제

번호 점수 조건
#16점

N ≦ 1000， P_i = -1 (1 ≦ i ≦ N)

#29점

N ≦ 1000， P_1 = -1， P_i = i-1 (2 ≦ i ≦ N)

#316점

N ≦ 1000， P_i < i (1 ≦ i ≦ N)．

#420점

P_i < i (1 ≦ i ≦ N)

#519점

N ≦ 1000

#630점

추가 제약 조건 없음


예제1

입력
67
124310100
-1-1-1-1-1-1
출력
4

정올이의 초기 집중력은 7입니다. 모든 i (1 ≦ i ≦ N)에 대해 P_i = -1이므로, 정올이는 집중력이 충분한 한 모든 공을 언제든지 구멍에 떨어뜨릴 수 있습니다.

예를 들어, 아래와 같은 방법으로 정올이는 공 4를 떨어뜨릴 수 있습니다.

  1. 먼저 공 3을 구멍에 떨어뜨립니다. 이때 정올이의 집중력은 4만큼 감소하고, 남은 집중력은 3이 됩니다.

  2. 그다음 공 4를 구멍에 떨어뜨립니다. 이때 정올이의 집중력은 3만큼 감소하고, 남은 집중력은 0이 됩니다.

  3. 공 5와 6은 이제 떨어뜨릴 수 없습니다.

따라서 정올이가 구멍에 떨어뜨릴 수 있는 공의 번호 중 가장 큰 값은 4입니다


예제2

입력
512
12358
-11234
출력
4

정올이의 초기 집중력은 12입니다. 아래와 같은 방식으로 정올이는 공 4를 구멍에 떨어뜨릴 수 있습니다:

  1. 공 1을 구멍에 떨어뜨립니다. (P_1 = -1이므로, 공 1은 언제든지 떨어뜨릴 수 있습니다.)

    • 정올이의 집중력은 1만큼 감소하고, 남은 집중력은 11이 됩니다.

  2. 공 2를 구멍에 떨어뜨립니다. (P_2 = 1이므로, 공 1이 이미 떨어졌으므로 공 2를 떨어뜨릴 수 있습니다.)

    • 정올이의 집중력은 2만큼 감소하고, 남은 집중력은 9가 됩니다.

  3. 공 3을 구멍에 떨어뜨립니다. (P_3 = 2이므로, 공 2가 이미 떨어졌으므로 공 3을 떨어뜨릴 수 있습니다.)

    • 정올이의 집중력은 3만큼 감소하고, 남은 집중력은 6이 됩니다.

  4. 공 4를 구멍에 떨어뜨립니다. (P_4 = 3이므로, 공 3이 이미 떨어졌으므로 공 4를 떨어뜨릴 수 있습니다.)

    • 정올이의 집중력은 5만큼 감소하고, 남은 집중력은 1이 됩니다.

  5. 이후 공 5를 떨어뜨릴 수 없습니다. (남은 집중력 1로는 공 5를 떨어뜨릴 수 없습니다.)

따라서 정올이가 구멍에 떨어뜨릴 수 있는 공 중 가장 큰 번호는 4입니다.

이 예시는 주어진 문제의 제약을 모두 만족하는 예시입니다.


예제3

입력
810
31415926
-112-14457
출력
7

예제4

입력
21000000000000000
11
21
출력
-1

예제5

입력
92468024680
123456789234567891345678912456789123567891234678912345789123456891234567912345678
654-132198
출력
6

태그

출처

JOI 2025 예선2

역링크