Description

DotR (Defense of the Robots) Allstars is a globally popular Warcraft map. Its rules are simple, similar to the also popular map DotA (Defense of the Ancients) Allstars.

In DotR, heroes have only one attribute — Strength. They need to buy equipment to improve their Strength. Each piece of equipment increases the hero’s Strength by a fixed amount, so the hero’s Strength equals the sum of the Strength values of all purchased equipment. There are two types of equipment: basic equipment and advanced equipment. Basic equipment can be purchased directly from the shop with gold, while advanced equipment must be crafted from basic equipment or lower-tier advanced equipment. Crafting requires no additional gold. The crafting dependency can be represented by a tree.

For example, Sange and Yasha is crafted from Sange, Yasha, and a Sange and Yasha Recipe Scroll. Sange itself is crafted from an Ogre Axe, a Belt of Giant Strength, and a Sange Recipe Scroll. Each basic equipment has a stock limit, which prevents you from crafting certain high cost-performance equipment infinitely.

Now, the hero Spectre has $M$ gold coins and wants to buy equipment to maximize his Strength. Can you help him? He will teach you the spell Haunt (幽灵附体) as a reward.

Description

Input Format

The first line contains two integers, $N$ ($1 \le N \le 51$) and $M$ ($0 \le M \le 2000$), representing the number of equipment types and the amount of gold, respectively. Equipment are numbered from $1$ to $N$.

The next $N$ lines, in the order of equipment $1$ to equipment $N$, each describe one equipment.

• The first nonnegative integer on each line is the Strength contributed by this equipment.
• The next character indicates whether this equipment is basic or advanced: A denotes advanced equipment, B denotes basic equipment.
  • If it is basic equipment, it is followed by two positive integers: its unit price (in gold) and its stock limit (no more than $100$).
  • If it is advanced equipment, it is followed by a positive integer $C$, indicating that this advanced equipment requires $C$ types of lower-tier equipment. The next $2C$ integers then describe, in order, for each lower-tier equipment, its type and the required quantity.

Output Format

Output a single integer $S$, the maximum total Strength that can be achieved.

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

Hint

Translated by ChatGPT 5