Nintendo Switch生产车间

题目描述

任天堂决定将Nintendo Switch发售日期定于2017年3月。

（图片来源：IT之家）

F工厂收到了任务，要在发售日期之前把许多其他厂商生产的部件总装成一部一部Nintendo Switch。

F工厂有n条生产线用于生产Nintendo Switch，每条生产线都能完成组装一部Nintendo Switch所需要的m道工序，只是需要的时间不同。另外产品可在不同的流水线上完成不同的工序且流水线切换时间及进出流水线时间忽略不计，但一件产品完成一道工序只能在同一条流水线上做，不能中断。

F工厂的老板向你们提出这样的问题：

已经知道，n条流水线完成m道工序所需要的时间各是多少。

那么，完成组装一部Nintendo Switch所需要的最短时间是多少？

输入

第一个数为数据组数T

接下来T组数据，每组数据由下述内容组成：

第一行为两个数，以一个空格分隔，n与m，n代表流水线数目，m代表总装Nintendo Switch所需要的工序数目。其中$1 \leq n \leq 1000$, $1 \leq m \leq 1000$

接下来n行，每行m个数，对于第i行的第j个数t，表示第i条流水线完成第j个工序需要t个单位时间。其中$t>0$，且t在int范围内。

输出

对于每组数据，输出一行，Case #X: A, 其中X代表第几组数据，A代表该组数据的答案，即F工厂完成生产一部Nintendo Switch的最短时间。

具体参见样例。

输入样例

2
1 2
1 2
2 3
5 6 7
4 8 2

输出样例

Case #1: 3
Case #2: 12

样例解释

对于第二组数据，最短时间12可由下述工序得出：

1. 在第2条流水线完成工序1，时间花费为4；
2. 在第1条流水线完成工序2，时间花费为6；
3. 在第2条流水线完成工序3，时间花费为2.

总时间：4+6+2=12

Hint

数据量很大，请使用scanf/printf进行输入输出操作。

思考题

若流水线间的切换、进入流水线、出流水线都需要时间，就像这样：（图片来源网络）

如果有2条流水线用于总装Nintendo Switch, 那么总装一部Nintendo Switch最快需要多少时间？3条呢？4条呢？