[JSOI2008]魔兽地图DotR

DotR（Defense of the Robots）Allstars 是一张风靡全球的魔兽地图，其规则与同样流行的地图 DotA（Defense of the Ancients）Allstars 类似。

在 DotR 中，英雄只有一个属性——力量。英雄可以购买装备来提升自己的力量值，每件装备都会使佩戴它的英雄增加固定的力量值，因此英雄的力量值等于其购买的所有装备所提供的力量值之和。

装备分为基本装备和高级装备两种。基本装备可以直接从商店中用金币购买；高级装备需要使用基本装备或较低级的高级装备合成，合成不需要额外花费金币。装备的合成关系可以用一棵树表示。

例如，Sange and Yasha 的合成需要 Sange、Yasha 和 Sange and Yasha Recipe Scroll 三种物品。其中，Sange 又需要 Ogre Axe、Belt of Giant Strength 和 Sange Recipe Scroll 合成。

每件基本装备都有数量限制，因此无法无限合成某些性价比很高的装备。现在，英雄 Spectre 有 $m$ 个金币，他想用这些钱购买装备，使自己的力量值尽量高。请你帮助他求出最多可以提升的力量值。

输入格式

第一行包含两个整数 $N$ 和 $m$ ，分别表示装备的种类数和金币数。装备使用 $1$ 到 $N$ 的整数编号。

接下来的 $N$ 行按照装备编号 $1$ 到 $N$ 的顺序，每行描述一种装备。

每行的第一个非负整数表示该装备贡献的力量值。

接下来是一个字符，表示该装备是基本装备还是高级装备：A 表示高级装备，B 表示基本装备。

如果是基本装备，接下来的两个正整数分别表示它的单价（单位为金币）和数量限制。
如果是高级装备，接下来首先是一个正整数 $C$ ，表示该高级装备需要 $C$ 种低级装备。随后给出 $2C$ 个整数，依次描述每种低级装备的编号和所需数量。低级装备的编号在 $1$ 到 $N$ 之间。

保证合成关系构成一片森林，即不存在循环依赖；森林以某些基本装备为叶节点，以高级装备为内部节点。保证所有装备最终均可由基本装备合成，或本身就是基本装备。

输出一个整数 $S$ ，表示最多可以提升的力量值。

保证答案不超过 $2^{31}-1$ 。

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

本题为 JSOI 2008 试题「魔兽地图 DotR」，题面与测试数据整理自 BZOJ。

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