당구

문제

비타로는 당구를 치며 놀고 있다. JOI 국의 당구는 당구대 위에 놓인 $N$ 개의 공 $1,2,...,N$ 을 사용하는 놀이이며, 당구대에는 공을 떨어뜨리기 위한 구멍이 있다. 한 번 구멍에 떨어진 공은 당구대 위로 되돌리지 않으며, 그 공을 다시 떨어뜨릴 수는 없다. 비타로의 목적은 가능한 한 큰 번호가 적힌 공을 구멍에 떨어뜨리는 것이다.

공을 떨어뜨리는 것은 집중을 필요로 하는 작업이다. 처음에 비타로의 집중력 은 $X$ 이며, 공 $i$ ($1 \le i \le N$) 를 떨어뜨리면 집중력이 $A_{i}$ 만큼 감소한다. 집중력이 $A_{i}$ 미만일 때는 공 $i$ 를 떨어뜨릴 수 없다.

또한, 이 당구에는 공을 떨어뜨리는 순서에 관한 규칙이 존재한다. 구체적으로는, $P_{i} = -1$ ($1 \le i \le N$) 일 때 공 $i$ 는 언제든지 떨어뜨릴 수 있고, $P_{i} \neq -1$ 일 때 공 $i$ 를 떨어뜨리기 위해서는 공 $P_{i}$ 가 이미 떨어져 있어야 한다.

비타로가 가진 집중력과 각 공의 정보가 주어졌을 때, 비타로가 공을 구멍에 떨어뜨릴 수 있는지 판정하고, 공을 떨어뜨릴 수 있는 경우에는 떨어뜨릴 수 있는 공의 번호의 최댓값을 구하는 프로그램을 작성하시오.

제한

• $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} \neq i$ ($1 \le i \le N$).
• 입력되는 값은 모두 정수이다.

서브태스크

1. ($6$ 점) $N \le 1000$, $P_{i} = -1$ ($1 \le i \le N$).
2. ($9$ 점) $N \le 1000$, $P_{1} = -1$, $P_{i} = i-1$ ($2 \le i \le N$).
3. ($16$ 점) $N \le 1000$, $P_{i} < i$ ($1 \le i \le N$).
4. ($20$ 점) $P_{i} < i$ ($1 \le i \le N$).
5. ($19$ 점) $N \le 1000$.
6. ($30$ 점) 추가 제약이 없다.

입력

입력은 다음 형식으로 주어진다.
$N$ $X$
$A_{1}$ $A_{2}$ $\dots$ $A_{N}$
$P_{1}$ $P_{2}$ $\dots$ $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 \le i \le 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$ 은 언제든지 떨어뜨릴 수 있다.) 비타로의 집중력이 $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$ 의 제약을 만족한다.

예제 입력 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_{1} = 2$ 이므로 공 $1$ 을 떨어뜨리기 위해서는 공 $2$ 가 이미 떨어져 있어야 한다. 반대로 $P_{2} = 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$ 의 제약을 만족한다.