{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\n\u003cp\u003e一个旅行者在城市之间旅行。在旅途中,他需要支付费用,同时也可以获得一些收入。\u003c/p\u003e\u003cp\u003e现在有n个城市,旅行者有m天时间进行旅行。每天他可以前往另一个城市,或者停留在当前城市并支付一些费用。当他到达一个城市时,他可以获得一些收入。即使他在城市停留,他也可以得到第二天的收入。所有收入每天都可能发生变化。旅行者总是从城市1出发。\u003c/p\u003e\u003cp\u003e现在轮到你找出最佳旅行方式,以最大化总收入。\u003c/p\u003e\n"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e存在多个案例。\u003c/p\u003e\u003cp\u003e每个案例的第一行是两个正整数,n和m。n是城市的数量,m是旅行的天数。接下来是n行,每行n个整数。第i行中的第j个整数表示从城市i到城市j的旅行费用。如果i等于j,则表示在该城市停留的费用。\u003c/p\u003e\u003cp\u003e空行之后有m行,每行有n个整数。第i行的第j个整数表示第i天从城市j获得的收入。\u003c/p\u003e\u003cp\u003e输入以两个零结束。\u003cbr\u003en,m\u0026lt;100。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"你必须为每个案例打印一行。即为最大收入。"}},{"title":"样例","value":{"format":"HTML","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\u003e3 3\r\n3 1 2\r\n2 3 1\r\n1 3 2\r\n\r\n2 4 3\r\n4 3 2\r\n3 4 2\r\n\r\n0 0\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e8\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"提示","value":{"format":"HTML","content":"在样例中,旅行者可以先去第2个城市,然后前往第1个城市,并在第1个城市结束旅行。总收入为:\u003cbr\u003e-1+4-2+4-1+4\u003d8;"}}]}