Merlin QA

Edythe is a young sorceress in the quality assurance department of Merlin, Inc., a magic spell factory. Her job is to test the spells that Merlin invents. Each spell consumes precise amounts of certain ingredients and turns them into other amounts of other ingredients. To check that a spell works, Edythe casts each spell exactly once.

She can cast a spell only when she holds every ingredient it requires. If she already made ingredients of the right kind with earlier spells, she must use those first. If she is still short, she takes exactly the missing amount from Merlin's storehouse, and ingredients taken from the storehouse cost her nothing. She starts with no ingredients at all, and she keeps everything she created and did not use.

Edythe wants the ingredients left at the end to be worth as much as possible. She has to cast each of the $N$ given spells exactly once, but she picks the order. Assuming every spell works as described, find the largest total value she can hold at the end.

For example, suppose the test plan holds these three spells.

1. Put in $7 worth of gold, get out $5 worth of sulfur.
2. Put in nothing, get out $10 worth of gold and $10 worth of sulfur.
3. Put in $20 worth of sulfur, get out $3 worth of gold and $2 worth of toads.

The first spell turns gold into sulfur, the second conjures gold and sulfur out of nothing, and the third turns sulfur into gold and toads.

Say Edythe casts them in the order 1, 2, 3. She fetches $7 worth of gold from the storehouse for the first spell. After the first two spells she holds $10 worth of gold and $15 worth of sulfur. The last spell needs $20 worth of sulfur, so she uses all the sulfur she has and fetches $5 more from the storehouse. She ends with $13 worth of gold and $2 worth of toads, $15 in total.

A better plan exists. Casting them in the order 3, 1, 2 leaves her $10 worth of gold, $15 worth of sulfur and $2 worth of toads, $27 in total.

The first line of the input gives the number of test cases $T$. The first line of each test case holds the number of spells $N$ and the number of ingredient kinds in the world $M$. Each of the next $N$ lines holds $M$ integers describing one spell. The $j$-th integer is the value of ingredient $j$. A negative integer is the dollar cost of an ingredient the spell consumes, a positive integer is the dollar value of an ingredient the spell produces, and a zero means the spell neither consumes nor produces that ingredient. No spell consumes and produces the same ingredient.

Limits

• $1 \le T \le 100$
• $1 \le N \le 100$
• $1 \le M \le 3$
• Every integer in a spell is between $-100$ and $100$.

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 largest value of ingredients Edythe can hold at the end.