닌자 배치

한 닌자 조직은 고객에게 닌자들을 배치하고, 닌자들이 그 고객을 위해 한 일에 대해 보수를 받는다.

이 조직에는 마스터라 불리는 닌자가 한 명 있고, 마스터를 제외한 모든 닌자는 정확히 한 명의 보스를 모신다. 닌자들의 비밀을 지키고 지휘 체계를 유지하기 위해, 오직 보스만이 자신의 부하에게 명령을 내릴 수 있으며, 그 외의 사람이 명령을 전달하는 것은 금지된다.

당신은 조직에서 닌자 몇 명을 모아 한 고객에게 배치하려고 한다. 배치된 각 닌자에게는 고정된 월급을 주며, 배치된 닌자들의 월급 총합은 주어진 예산을 넘을 수 없다. 명령을 전달하기 위해 당신은 닌자 한 명을 매니저로 정하고, 그 매니저는 배치된 모든 닌자에게 명령을 아래로 전달할 수 있어야 한다. 명령은 지휘 체계를 따라 아래로 내려가므로, 배치되는 닌자는 매니저 자신이거나 매니저의 (직접 또는 간접) 부하여야 한다. 명령은 배치되지 않은 닌자를 거쳐 전달될 수도 있다. 매니저 자신은 배치될 수도, 배치되지 않을 수도 있으며, 배치되지 않은 닌자에게는 월급을 주지 않는다.

당신은 예산 안에서 고객의 만족도를 최대로 하려고 한다. 고객의 만족도는 배치된 닌자의 총 수와 매니저의 리더십 레벨의 곱이다. 각 닌자의 리더십 레벨은 고정되어 있다.

각 닌자 $i$ ($1 \le i \le N$)에 대해 보스 $B_i$, 월급 $C_i$, 리더십 레벨 $L_i$가 주어지고, 월급으로 쓸 수 있는 예산 $M$이 주어질 때, 매니저와 배치할 닌자를 조건에 맞게 골랐을 때 고객 만족도의 최댓값을 출력하는 프로그램을 작성하시오.

첫째 줄에 두 자연수 $N$과 $M$이 공백을 사이에 두고 주어진다. $N$은 닌자의 수, $M$은 총 예산이다.

다음 $N$개의 줄에는 각 닌자의 정보가 주어진다. $i+1$번째 줄에는 세 정수 $B_i$, $C_i$, $L_i$가 공백을 사이에 두고 주어진다. $B_i$는 닌자 $i$의 보스, $C_i$는 닌자 $i$의 월급, $L_i$는 닌자 $i$의 리더십 레벨이다. $B_i = 0$이면 닌자 $i$는 마스터이다. 항상 $B_i < i$이므로, 각 닌자의 보스 번호는 그 닌자의 번호보다 작다.

고객 만족도의 최댓값을 출력한다.

• $1 \le N \le 100{,}000$
• $1 \le M \le 1{,}000{,}000{,}000$
• $0 \le B_i < i$
• $1 \le C_i \le M$
• $1 \le L_i \le 1{,}000{,}000{,}000$

예제에서 닌자 $1$을 매니저로 정하고 닌자 $3$과 $4$를 배치하면, 월급의 합은 $2 + 2 = 4$로 예산 $4$를 넘지 않는다. 배치된 닌자가 $2$명이고 매니저의 리더십 레벨이 $3$이므로, 고객의 만족도는 $2 \times 3 = 6$이며, 이 값이 최댓값이다.