Merlin QA (Large)

Edythe is a young sorceress in the quality assurance department of Merlin, Inc., a spell factory. Her job is to test the spells Merlin invents. A spell needs an exact amount of each of its input ingredients and turns them into exact amounts of other ingredients. To confirm that every spell works, Edythe has to cast each one exactly once.

She can cast a spell only when she holds the required amount of every input ingredient. If earlier spells already produced ingredients of the right kind, she must use those first. Whatever is still missing she takes from Merlin's storehouse, and the storehouse charges her nothing. She starts with no ingredients, and she keeps everything she produced and did not use.

Edythe wants her apprenticeship to pay as well as possible. She has to cast each of the $N$ given spells exactly once, and she is free to choose the order. Every spell works as described. Find the largest total value of ingredients she can hold once all of them have been cast.

All amounts are measured in dollars. Suppose the test plan holds these 3 spells over the ingredients gold, sulfur and toads.

1. Consumes gold worth 7 dollars, produces sulfur worth 5 dollars.
2. Consumes nothing, produces gold worth 10 dollars and sulfur worth 10 dollars.
3. Consumes sulfur worth 20 dollars, produces gold worth 3 dollars and toads worth 2 dollars.

Cast in the order 1, 2, 3, Edythe first fetches gold worth 7 dollars from the storehouse for the first spell and gets sulfur worth 5 dollars. After the second spell she holds gold worth 10 dollars and sulfur worth 15 dollars. The third spell needs sulfur worth 20 dollars, so she spends all 15 dollars of it and fetches the missing 5 dollars from the storehouse. She ends with gold worth 13 dollars and toads worth 2 dollars, 15 dollars in total.

The order 3, 1, 2 is better. The third spell is cast while she holds nothing, so all of its sulfur comes from the storehouse and none of the sulfur she makes later is ever spent. She ends with gold worth 10 dollars, sulfur worth 15 dollars and toads worth 2 dollars, 27 dollars in total.

The first line holds the number of test cases, $T$. Each test case starts with a line holding $N$ and $M$, where $M$ is the number of kinds of ingredients in the world. Each of the next $N$ lines describes one spell with $M$ integers. The $j$-th integer is the value of the $j$-th ingredient for that spell: a negative integer is the dollar cost of an input ingredient, a positive integer is the dollar value of an output ingredient, and a zero means the spell neither consumes nor produces it. No spell consumes and produces the same ingredient.

Limits

• $1 \le T \le 100$
• $1 \le N \le 100$
• $1 \le M \le 8$
• 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 total value of ingredients Edythe can hold after casting all $N$ spells.