[Apio2012]dispatching

在一个忍者帮派中，一些忍者会被选中派遣给顾客，并根据自己的工作获得报酬。帮派中有一名忍者被称为 Master。除 Master 外，每名忍者都有且仅有一名直接上级。

为了保密并增强忍者们的领导力，所有与工作相关的指令都必须由上级发送给自己的直接下属，不能通过其他方式传递。现在，你需要招募一批忍者并将他们派遣给顾客。

对于每一名被派遣的忍者，你需要支付一定的薪水，并且支付的薪水总额不能超过预算。为了发送指令，你还需要选择一名忍者作为管理者，要求该管理者能够向所有被派遣的忍者发送指令。在发送指令时，任何忍者，无论是否被派遣，都可以作为消息的传递者。管理者可以被派遣，也可以不被派遣；如果管理者没有被派遣，则不需要支付其薪水。

你的目标是在预算内使顾客的满意度最大。顾客的满意度定义为被派遣的忍者总数乘以管理者的领导力水平，其中每名忍者都有一个确定的领导力水平。

给定每名忍者 $i$ 的上级 $B_i$、薪水 $C_i$、领导力 $L_i$，以及支付给所有忍者的薪水总预算 $M$，请计算在满足条件的情况下顾客满意度的最大值。

输入格式

从标准输入读入数据。

第一行包含两个整数 $N$ 和 $M$，其中 $N$ 表示忍者的个数，$M$ 表示薪水总预算。

接下来 $N$ 行描述每名忍者的上级、薪水以及领导力。第 $i$ 行包含三个整数 $B_i$、$C_i$ 和 $L_i$，分别表示第 $i$ 个忍者的上级编号、薪水以及领导力。

Master 满足 $B_i=0$，并且每名忍者的上级编号都小于自己的编号，即 $B_i<i$。

输出格式

输出一个整数，表示在预算内能够获得的顾客满意度最大值。

样例输入

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

样例输出

6

样例解释

选择编号为 $1$ 的忍者作为管理者，并派遣编号为 $3$ 和 $4$ 的忍者。支付的薪水总和为 $4$，没有超过预算。派遣了 $2$ 名忍者，管理者的领导力为 $3$，因此顾客满意度为 $2\times 3=6$，这是能够获得的最大满意度。

数据范围

• $1\le N\le 10^5$，忍者的个数；
• $1\le M\le 10^9$，薪水总预算；
• $0\le B_i<i$，忍者 $i$ 的上级编号；
• $1\le C_i\le M$，忍者 $i$ 的薪水；
• $1\le L_i\le 10^9$，忍者 $i$ 的领导力水平。

来源与许可

本题为 APIO 2012 试题「Dispatching」，题面与测试数据整理自 BZOJ 2809。

样例 1

输入

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

输出

6