{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\n今天,街头上有相当多的汽车、摩托车、卡车和其他车辆都急需翻新。你接下了这个工作,顺便从一家大电视台那里赚了几美元。当然,有很多工作要做,你已经觉得有点吃不消了。因此,你想让车库来完成各种工作,如油漆、内饰装修等。不幸的是,这些车库都非常专业,所以你需要不同的车库来做不同的工作。更糟糕的是,他们往往会根据车的整体外观来收费。也就是说,如果一辆车的内饰全是皮革,油漆工可能会收更多的费用。由于这些\"附加费\"取决于做什么工作以及之前完成了哪些工作,你现在正在试图通过找到这些工作的最优顺序来节省钱。\n\n各个工作的编号为 **1** 到 **n**。给定每项工作的基础价格 **p** 和每对工作 **(i, j)** 的附加费 **s**,也就是说,如果工作 **j** 已经完成,你必须为工作 **i** 额外支付 **s**,你需要计算完成所有工作所需的最低总成本。\n\n"}},{"title":"输入","value":{"format":"MD","content":"输入以一个整数 **T (\u0026#8804; 100)** 开始,表示测试用例的数量。\n\n每个用例开始时有一个整数 **n (1 \u0026#8804; n \u0026#8804; 14)**,表示工作的数量。然后是 **n** 行,每行包含恰好 **n** 个整数。**i\u003csup\u003eth\u003c/sup\u003e** 行包含了在车库编号 **i** 中完成第 **i\u003csup\u003eth\u003c/sup\u003e** 项工作以及该工作的基础价格所需支付的附加费。更准确地说,在 **i\u003csup\u003eth\u003c/sup\u003e** 行,第 **i\u003csup\u003eth\u003c/sup\u003e** 个整数是工作 **i** 的基础价格,第 **j\u003csup\u003eth\u003c/sup\u003e** 个整数 **i \u0026#8800; j** 是工作 **i** 的附加费,如果工作 **j** 已经完成的话。价格将是小于或等于 **100000** 的非负整数。"}},{"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\n2\n10 10\n9000 10\n3\n14 23 0\n0 14 0\n1000 9500 14\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 30\nCase 2: 42\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}