题目描述

DotR 游戏中英雄通过购买装备提升力量值。装备分为：

• 基本装备：直接用金币购买，有单价和数量限制
• 高级装备：由基本装备或其他高级装备合成，无需额外金币

装备合成关系构成一棵树。给定金币数 $m$，求英雄能获得的最大力量值。

输入格式

第一行：$n$（装备种类数），$m$（金币数）

接下来 $n$ 行，按装备 $1$ 到 $n$ 的顺序描述：

• 第一个数：装备的力量值
• 一个字符：A（高级装备）或 B（基本装备）
• 基本装备：单价、数量限制
• 高级装备：需要的低级装备数 $C$，接着 $2C$ 个数（装备种类和需要的个数）

输出格式

一个整数：最大力量值

样例

输入

10 59
5 A 3 6 1 9 2 10 1
1 B 5 3
1 B 4 3
1 B 2 3
8 A 3 2 1 3 1 7 1
1 B 5 3
5 B 3 3
15 A 3 1 1 5 1 4 1
1 B 3 5
1 B 4 3

输出

33

数据范围与提示

对于 $100\%$ 的数据：

• $1 \leq n \leq 51$
• $0 \leq m \leq 2000$