{"trustable":false,"sections":[{"title":"题目描述","value":{"format":"MD","content":"47号特工正在执行一项危险的任务 `击败黑色怪物-15`。这是一项秘密任务,因此47的武器供应有限。他只有一把老式武器 `KM .45 Tactical (USP)`。任务听起来很简单--他最多将遇到15个目标,他必须将他们全部杀死。主要困难在于武器。经过反复计算,他找到了一条出路。在击败一个目标后,他可以**使用该目标的武器杀死其他目标**。因此,必须有一个击杀目标的顺序,使武器射击的**总次数最少** 。作为47号特工的个人程序员,您必须计算出杀死所有目标所需的最少射击次数。\n\n现在给您一个列表,显示每种武器每次射击对每个目标造成的伤害,您也知道每个目标的生命值。当一个目标的生命值降到 $0$ 或更低时,他就被杀死了。47开始时只使用 `KM .45 Tactical (USP)`,它对任何目标每次射击的伤害都是 $1$。该列表表示为二维矩阵,其中第 $i$ 个元素包含 $N$ 个个位数$(\u00270\u0027-\u00279\u0027)$,表示从目标 $i$ 处获得的武器对目标 $0、1、2......、N-1$ 造成的伤害,健康值表示为一系列 $N$ 个整数,其中第 $i$ 个元素表示该目标的健康值。\n\n**给定代表所有武器伤害的列表,以及每个目标的生命值,您应该找出杀死所有目标所需的最少射击次数。**"}},{"title":"输入格式","value":{"format":"MD","content":"输入以整数 $T(≤40$)开始,表示测试用例数。\n\n每个案例以空行和整数 $N(1≤N≤15)$开始。下一行包含N个空格分隔的介于 $1$ 和 $10^6$ 之间的整数,表示目标的健康度 $0, 1, 2, ..., N-1$。接下来的N行中每行包含N个数字。第 $i$ 行的第 $j$ 位数字表示在每次射击中使用目标 $i$ 的武器时对目标 $j$ 造成的伤害。"}},{"title":"输出格式","value":{"format":"MD","content":"对于每一个输入案例,您必须打印案例编号以及杀死所有目标所需的最少射击次数。"}},{"title":"样例","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\n\n3\n10 10 10\n010\n100\n111\n\n3\n3 5 7\n030\n500\n007\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 30\nCase 2: 12\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}