Edythe 是一位年轻的魔法师，在 Merlin 公司（一家魔法咒语工厂）的质量保证部门工作。她的工作是测试 Merlin 本人发明的魔法咒语。每个咒语都需要精确数量的特定原料，并将它们转化为其他数量的其他原料。Edythe 的工作是精确地施展每个咒语一次，以验证咒语是否正常工作。

她只有在拥有每种原料所需数量时才能施展咒语。如果她已经从之前的咒语中创造出了合适类型的原料，Edythe 必须先使用这些原料。然而，如果她仍然需要更多原料，她可以从 Merlin 的仓库中获取。她开始时没有任何原料，但在最后，她可以保留所有她创造出来且未使用的额外原料。

Edythe 希望从她的学徒生涯中获得尽可能多的利润！她必须精确地施展给定的 $N$ 个咒语各一次，但她可以自由选择施展顺序。假设每个咒语都按预期工作，哪种顺序能让她最终获得最多的金钱？

例如，假设测试计划包含以下 3 个咒语：

1. 输入：价值 $\$7$ 的黄金。输出：价值 $\$5$ 的硫磺。
2. 输入：无。输出：价值 $\$10$ 的黄金，价值 $\$10$ 的硫磺。
3. 输入：价值 $\$3$ 的黄金，价值 $\$20$ 的硫磺。输出：价值 $\$2$ 的蟾蜍。

注意，第一个咒语将黄金转化为硫磺，第二个咒语凭空变出黄金和硫磺，第三个咒语将黄金和硫磺转化为蟾蜍。

如果 Edythe 按 1, 2, 3 的顺序施展这些咒语，她首先会从仓库中获取价值 $\$7$ 的黄金用于咒语 #1。这将使她能够施展咒语 #1 和 #2，得到价值 $\$10$ 的黄金和 $\$15$ 的硫磺。对于最后一个咒语，她需要价值 $\$3$ 的黄金和 $\$20$ 的硫磺。她必须用掉到目前为止创造的所有硫磺、价值 $\$3$ 的黄金，以及从仓库中额外获取的价值 $\$5$ 的硫磺。这会让她在最后剩下价值 $\$9$ 的原料（价值 $\$7$ 的黄金和价值 $\$2$ 的蟾蜍）。

但有一个更好的计划。如果她按 3, 1, 2 的顺序施展咒语，她最终将拥有价值 $\$27$ 的原料（价值 $\$10$ 的黄金、价值 $\$15$ 的硫磺和价值 $\$2$ 的蟾蜍）。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含 $N$ 和 $M$。$M$ 是世界上原料的种类数。接下来的 $N$ 行，每行包含 $M$ 个整数，描述一个咒语。每个整数是相应原料的价值（或成本）。负整数是输入原料的美元成本；正整数是输出原料的美元价值；零表示该咒语既不产生也不消耗该原料。这也意味着没有咒语可以同时消耗和产生同一种原料。

输出格式

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是 Edythe 最后能拥有的原料的最大价值。

数据范围

$1 \le T \le 100$ $1 \le N \le 100$ $-100 \le$ 每个咒语中的每个整数 $\le 100$

小数据范围

$1 \le M \le 2$

大数据范围

$1 \le M \le 8$

样例

输入 1

2
3 1
1
0
-1
3 3
-7 5 0
10 10 0
3 -20 2

输出 1

Case #1: 1
Case #2: 27