Karen and Supermarket

Karen은 집으로 가는 길에 식료품을 사기 위해 슈퍼마켓에 들르기로 했다.

Karen은 많은 상품을 사야 하지만, 학생이기 때문에 예산이 여전히 상당히 제한되어 있다. 실제로 Karen은 최대 b달러까지만 쓸 수 있다.

슈퍼마켓에서는 n개의 상품을 판매한다. i-th 상품은 ci달러에 살 수 있다. 물론 각 상품은 한 번만 살 수 있다.

최근 슈퍼마켓은 매출을 늘리려고 하고 있다. 단골 고객인 Karen은 n개의 쿠폰을 받았다. If Karen가 i-th 상품을 구매하면, i-th 쿠폰을 사용하여 가격을 di만큼 낮출 수 있다. 물론 해당 상품을 구매하지 않고 쿠폰을 사용할 수는 없다.

하지만 쿠폰에는 제약 조건이 있다. 모든 i ≥ 2에 대해, i-th 쿠폰을 사용하려면 Karen은 xi-th 쿠폰도 사용해야 한다. 이는 해당 쿠폰의 조건을 충족하기 위해 더 많은 쿠폰을 사용해야 할 수도 있음을 의미한다.

Karen은 다음을 알고 싶어 한다. 예산 b을 초과하지 않으면서 살 수 있는 상품의 최대 개수는 얼마인가?

입력의 첫 번째 줄에는 두 정수 n와 b가 주어진다 (1 ≤ n ≤ 5000, 1 ≤ b ≤ 109). 이들은 각각 상점에 있는 상품의 개수와 Karen이 가진 금액을 나타낸다.

다음 n개의 줄에는 상품에 대한 설명이 주어진다. 구체적으로 다음과 같다.

• 이 줄들 중 i-th 줄은 두 정수 ci와 di로 시작한다 (1 ≤ di < ci ≤ 109). 이들은 각각 i-th 상품의 가격과 i-th 상품의 쿠폰을 사용할 때의 할인액을 나타낸다.
• i ≥ 2이면, 그 뒤에 정수 xi가 하나 더 주어진다 (1 ≤ xi < i). 이는 이 쿠폰을 사용하려면 xi-th 쿠폰도 사용해야 함을 나타낸다.

Karen이 예산을 초과하지 않으면서 살 수 있는 서로 다른 상품의 개수를 한 줄에 정수 하나로 출력한다.

첫 번째 테스트 케이스에서 Karen은 다음 4개의 상품을 구매할 수 있다.

• 첫 번째 쿠폰을 사용하여 첫 번째 상품을 10 - 9 = 1달러에 구매한다.
• 세 번째 쿠폰을 사용하여 세 번째 상품을 12 - 2 = 10달러에 구매한다.
• 네 번째 쿠폰을 사용하여 네 번째 상품을 20 - 18 = 2달러에 구매한다.
• 여섯 번째 상품을 2달러에 구매한다.

이 상품들의 총비용은 15이며, Karen의 예산 이내이다. 예를 들어 Karen은 여섯 번째 상품에 쿠폰을 사용할 수 없다는 점에 유의한다. 그렇게 하려면 다섯 번째 쿠폰도 사용하여 다섯 번째 상품을 구매했어야 하지만, 여기서는 그렇게 하지 않았기 때문이다.

두 번째 테스트 케이스에서 Karen은 모든 쿠폰을 사용하고 모든 상품을 구매하기에 충분한 돈을 가지고 있다.