배낭

헨젤과 그레텔이 여행을 떠난다. 소년 헨젤은 그레텔에게 잘 보이고 싶어서 두 사람의 짐을 배낭 하나에 모두 담기로 했다. 게다가 배낭이 무거울수록 더 좋은 인상을 줄 수 있다. 물론 헨젤이 집에 있는 물건을 아무 생각 없이 다 담을 수는 없다. 그러면 배낭이 찢어질 수도 있어서 큰 망신이 될 것이기 때문이다.

또한 헨젤은 예컨대 라디오는 챙기면서 건전지는 두고 오거나, 삼각대는 가져가면서 카메라는 잊어버리는 상황을 만들어서는 안 된다. 각 물건 $i$에 대해 헨젤은, 그 물건이 없으면 물건 $i$가 쓸모없어지는 다른 물건 $j$를 지정했거나, 아니면 물건 $i$가 그 자체로 유용한 물건이라고 표시해 두었다.

배낭의 최대 적재량을 넘기지 않으면서, 그리고 쓸모없는 물건을 하나도 가져가지 않으면서, 헨젤이 만들 수 있는 배낭 내용물의 최대 무게를 구하여라.

첫 번째 줄에는 두 정수 $n$과 $p$ ($1 \le n \le 200$, $1 \le p \le 10^6$)가 주어진다. 이는 각각 헨젤이 가져갈지 고민하는 물건의 개수와 배낭의 적재량(킬로그램 단위)을 뜻한다. 담은 물건들의 무게 합이 $p$를 넘으면 배낭이 찢어진다.

물건은 $1$번부터 $n$번까지 번호가 매겨져 있다고 하자. 이어지는 $n$개의 줄에는 각 물건의 정보가 주어진다. $i$번 물건의 정보는 두 정수 $j_i$와 $m_i$ ($0 \le j_i < i$, $1 \le m_i \le p$)로 이루어진다. $j_i$는 물건 $i$를 담기 위해 반드시 배낭에 함께 들어 있어야 하는 물건의 번호이며($j_i = 0$이면 물건 $i$는 아무 조건 없이 담을 수 있다), $m_i$는 물건 $i$의 무게(킬로그램)이다.

헨젤이 만들 수 있는 배낭 내용물의 최대 무게(킬로그램)를 나타내는 정수 하나를 출력하여라.