정올이는 당구장에서 놀고 있다. 당구장은 테이블 위에 놓인 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가 이미 떨어져 있어야 한다.

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

#8229 upload 15 done 7 how_to_reg 7 call_split Subtask

당구장 timer 1s memory 1024MB

#8229
Subtask

당구장 1s 1024MB