{"trustable":false,"sections":[{"title":"","value":{"format":"MD","content":"YZX是一位从不失手的职业杀手。\n\n一天,PZY委托YZX完成一项危险的刺杀任务。这是一项秘密任务,因此YZX的武器供应有限。他只有一把初始武器。任务很简单:他最多将遇到15个目标,他必须将他们全部杀死。\n\n但是PZY是个追求完美的人。她希望YZX能尽快完成任务。她得知,每个目标都随身携带一把武器。在击败一个目标后,他可以使用该目标的武器杀死其他目标。但因为各种原因,一把武器对不同目标造成的伤害是不同的。现在,PZY想让YZX以一个最优的顺序依次击杀所有目标,使武器射击的总次数最少。但PZY只擅长生物学,YZX只擅长杀人,他们都难以完成这个规划。所以PZY找到了你,她请求你计算出杀死所有目标所需的最少射击次数。\n\n现在给你一个列表,显示每种武器每次射击对每个目标造成的伤害,你也知道每个目标的生命值。当一个目标的生命值降到0或更低时,他就被杀死了。YZX开始时只使用一把伤害为1的初始武器。该列表表示为二维矩阵,其中第i个元素包含N个个位数(\u00270\u0027-\u00279\u0027),表示从目标i处获得的武器对目标0、1、2......、N-1造成的伤害,生命值表示为一系列N个整数,其中第i个元素表示该目标的生命值。\n\n给定代表所有武器伤害的列表,以及每个目标的生命值,您应该找出杀死所有目标所需的最少射击次数。"}},{"title":"Input","value":{"format":"MD","content":"输入以整数T(≤40)开始,表示测试用例数。\n\n每个案例以空行和整数N(1≤N≤15)开始。下一行包含N个空格分隔的介于1和106之间的整数,表示目标的生命值0, 1, 2, ..., N-1。接下来的N行中每行包含N个数字。第i行的第j位数字表示在每次射击中使用目标i的武器时对目标j造成的伤害。"}},{"title":"Output","value":{"format":"MD","content":"共T行:\n对于每一个输入案例,输出格式为: Case 案例编号: 杀死所有目标所需的最少射击次数 \n注意空格的分布(详见样例)。"}},{"title":"Sample","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"}}]}