En una secta de ninjas, los ninjas son enviados a un cliente y son recompensados ​​de acuerdo con su trabajo.

En esta secta, hay un ninja llamado Maestro. Cada ninja, excepto el Maestro, tiene un solo jefe. Para preservar la confidencialidad y fomentar el liderazgo, las instrucciones relativas a su trabajo siempre son enviadas por un jefe a sus subordinados. Está prohibido enviar instrucciones por otros métodos.

Estás reuniendo a varios ninjas y los envías a un cliente. Tienes que pagar salarios a los ninjas enviados. Para cada ninja, la cantidad de salario para él / ella es fija. El monto total de los salarios que se les paga debe estar dentro de un presupuesto. Además, para enviar instrucciones, debes elegir un ninja como administrador que pueda enviar instrucciones a todos los ninjas enviados. Cuando se envían instrucciones, un ninja que no sea enviado puede mediar en la transmisión. El manager puede o no ser enviado. Si no se envía al manager, no se le pagará.

Le gustaría maximizar el nivel de satisfacción del cliente tanto como sea posible dentro de un presupuesto. El nivel de satisfacción del cliente se calcula como el producto del número total de ninjas enviados y el nivel de liderazgo del manager. Para cada ninja, su nivel de liderazgo es fijo.

Escriba un programa que, dado el jefe ~b[i]~, la cantidad de salario ~c[i]~, el nivel de liderazgo ~l[i]~ de cada ninja ~i (1 \leq i \leq n)~ y el presupuesto para salarios ~m~, genere el valor máximo del nivel de satisfacción del cliente. cuando el manager y los ninjas despachados son elegidos para que se cumplan todas las condiciones.

Entrada

La primera línea contiene el número de ninjas ~n (1 \leq n \leq 10^5)~ y el presupuesto ~m (1 \leq m \leq 10^9)~. Las siguientes ~n~ líneas describen el jefe, el salario y el nivel de liderazgo de cada ninja. La ~(i + 1)~ -ésima línea contiene tres enteros separados por espacios ~b[i]~, ~c[i]~, ~l[i]~, que describen que el jefe de ninja ~i~ es ninja ~b[i]~, la cantidad de su salario es ~c[i]~ y su nivel de liderazgo es ~l[i]~. El ninja ~i~ es el Maestro si ~b[i] = 0~. Dado que la desigualdad ~b[i] < i~ siempre se satisface, para cada ninja, el número de su jefe es siempre menor que el número de sí mismo.

Salida

Escriba el valor máximo del nivel de satisfacción del cliente en la salida estándar.

Ejemplo de Entrada

5 4
0 3 3
1 3 5
2 2 2
1 2 4
2 3 1

Ejemplo de Salida

6

Explicación del ejemplo

Si elegimos al ninja 1 como manager y ninja 3, 4 como ninjas enviados, la cantidad total de salarios es 4, lo que no excede el presupuesto 4. Dado que el número de ninjas enviados es 2 y el nivel de liderazgo del manager es 3, el nivel de satisfacción del cliente es 6. Este es el valor máximo.