당구

면접 대비

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

요약

각 공은 선행 공을 먼저 떨어뜨려야 합니다. 자기 자신과 선행 공들의 A 합이 X 이하인 공 중 가장 큰 번호를 구합니다.

난이도: 쉬움10점 중 3점
유형: 트리, 누적 합
정답자: 아직 제출이 없습니다

문제

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

공을 떨어뜨리는 일에는 집중력이 필요하다. 처음에 비타로의 집중력은 $X$ 이고, 공 $i$ ( $1 \le i \le N$ )를 떨어뜨리면 집중력이 $A_i$ 만큼 줄어든다. 집중력이 $A_i$ 보다 작으면 공 $i$ 를 떨어뜨릴 수 없다.

떨어뜨리는 순서에도 규칙이 있다. $P_i = -1$ 이면 공 $i$ 는 언제든지 떨어뜨릴 수 있다. $P_i \ne -1$ 이면 공 $i$ 를 떨어뜨리기 전에 공 $P_i$ 가 이미 떨어진 상태여야 한다.

비타로의 집중력과 각 공의 정보가 주어질 때, 공을 하나라도 떨어뜨릴 수 있는지 판정하라. 떨어뜨릴 수 있다면 떨어뜨릴 수 있는 공 번호의 최댓값을 구하라.

입력

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

N X
A1 A2 … AN
P1 P2 … PN

출력

비타로가 구멍에 떨어뜨릴 수 있는 공 번호의 최댓값을 한 줄에 출력하라. 공을 하나도 떨어뜨릴 수 없다면 대신 $-1$ 을 출력하라.

제한

$1 \le N \le 200000$ .
$1 \le X \le 10^{15}$ .
$1 \le A_i \le 10^{9}$ ( $1 \le i \le N$ ).
$P_i = -1$ 또는 $1 \le P_i \le N$ ( $1 \le i \le N$ ).
$P_i \ne i$ ( $1 \le i \le N$ ).
입력되는 값은 모두 정수이다.

예제5

예제 1
입력
```
6 7
1 2 4 3 10 100
-1 -1 -1 -1 -1 -1
```
예상 출력
```
4
```
예제 2
입력
```
5 12
1 2 3 5 8
-1 1 2 3 4
```
예상 출력
```
4
```

예제 3

입력

8 10
3 1 4 1 5 9 2 6
-1 1 2 -1 4 4 5 7

예상 출력

예제 4
입력
```
2 1000000000000000
1 1
2 1
```
예상 출력
```
-1
```

예제 5

입력

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

예상 출력