题目内容

你正在玩一款游戏，游戏中有一个技能树系统。每个技能都有：

• 学习所需的时间成本（小时）
• 提升的战斗力（无重复）
• 前置技能（必须先学习的技能）

你有有限的总学习时间 $T$ ，需要在技能树中选择一条最优的学习路径，使得在时间限制内获得最大总战斗力。

输入描述

第一行：两个整数 $N$ 和 $T$

• $N$ ：技能数量（ $1$ $\leq$ $N$ $\leq$ $100$ ）
• $T$ ：总可用时间（ $1$ $\leq$ $T$ $\leq$ $1000$ ）

接下来 $N$ 行：每行描述一个技能（各字段之间以空格分隔）

• 技能编号： $1$ 到 $N$
• $time$ ：学习时间（ $1$ $\leq$ $time$ $\leq$ $100$ ）
• $power$ ：提升的战斗力值（ $1$ $\leq$ $power$ $\leq$ $1000$ ）
• $k$ ：前置技能数量（ $0$ $\leq$ $k$ $\leq$ $1$ ）
• 前置技能编号（如果有）

输出描述

输出一个整数：在时间 $T$ 内能获得的最大战斗力。

如果在时间 $T$ 内无法完成任意一个技能（例如 $T$ = $1$ ，任意一个技能学习时间均大于 $1$ ），则输出 $0$ 。

样例1

输入

2 1
1 2 15 0
2 4 20 0

输出

0

说明

学习技能 $1$ 、 $2$ 所需要的时间均大于总学习时间 $1$ ，无法完成任意技能的学习，因此输出 $0$ 。

样例2

输入

4 8
1 3 25 0
2 4 30 0
3 5 40 1 1
4 2 20 1 2

输出

65

说明

• 学习技能 $1$ ( $3$ $h$, $25$ $p$) $+$ 技能 $3$ ( $5$ $h$, $40$ $p$) = $8$ $h$，总战斗力 $65$ ；
• 学习技能 $1$ ( $3$ $h$, $25$ $p$) $+$ 技能 $4$ ( $2$ $h$, $20$ $p$) = $7$ $h$，总战斗力 $55$ ；
• 学习技能 $2$ ( $4$ $h$, $30$ $p$) $+$ 技能 $4$ ( $2$ $h$, $20$ $p$) = $6$ $h$，总战斗力 $50$ ；

最终得到的最大总战斗力为 $65$ 。

提示

• 每个技能只列出其直接前置技能。
• 每个技能最多只有 $1$ 个直接前置技能（ $k$ $\leq$ $1$ ），且输入保证依赖关系不形成环。