Quelling Blade

A hero is playing a game in which the strongest weapon is the Quelling Blade. Every type of weapon has a benefit value $B$ and a cost $C$. Benefits add up: if the hero owns two weapons with benefits $3$ and $5$, his current benefit is $3 + 5 = 8$. Owning several weapons of the same type stacks their benefits as well.

To buy a weapon, the hero may first need other weapons. For example, if a weapon requires two Demon Edges, the hero must already own two Demon Edges before buying it; buying a second copy of that weapon requires two more Demon Edges. A required weapon is not consumed when the purchase is made, and one weapon type may require several weapons of the same type. Each weapon type is required by at most one other weapon type, so the dependencies form a tree rooted at the Quelling Blade.

The hero earns exactly $1$ coin per second and spends coins to buy weapons; a weapon of cost $C$ can be bought once the hero has accumulated $C$ unspent coins. Because he must pay for the whole tree of prerequisites, the minimum time to obtain the Quelling Blade equals the total cost of every weapon he has to buy, and this minimum is reached no matter which valid buying order he follows.

The hero is a perfectionist: among all buying orders that reach the Quelling Blade in this minimum time, he wants to maximize the utility, defined as the sum, over each second from the start of the game up to (but not including) the second in which he obtains the Quelling Blade, of the total benefit he currently owns. Equivalently, a weapon whose purchase completes at time $t$ contributes its benefit during each of the $S - t$ seconds that remain before the Quelling Blade is obtained, where $S$ is the total buying time.

Report the maximum possible utility.

The first line contains the number of test cases $T$. Most test cases are small.

For each test case, the first line contains a single integer $N$, the number of weapon types $(1 \le N \le 1000)$.

The weapons are then described one by one. For weapon $i$ (weapons are numbered from $1$ to $N$):

• a line with two integers $B$ and $C$, its benefit value and cost $(1 \le B, C \le 2^{31}-1)$;
• a line with a single integer $P$, the number of distinct weapon types it requires;
• $P$ lines, each with two integers $I$ and $A$, meaning this weapon requires $A$ weapons of type $I$.

Weapon $1$ is the Quelling Blade. The total number of weapons that must be bought to obtain one Quelling Blade is less than $10^6$, and each weapon type is required by at most one other weapon type.

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from $1$ and $y$ is the maximum utility. The answer always fits in a signed 64-bit integer.