{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\u003cp\u003e一个旅行者在城市间旅行。他必须为此付出代价,但同时还能获得一些收入。\u003c/p\u003e\u003cp\u003e现在有n个城市,旅行者有m天的旅行时间。每天他都可能去另一个城市或呆在那里并支付一些钱。当他来到一个城市,他可以得到一些钱。如果他呆在城里,他可以得到第二天的收入。所有的收入可能每天都在变化。旅行者总是从城市1出发。 \u003c/p\u003e\u003cp\u003e现在请你去寻找最佳的旅行方式,使总收入最大化。\u003c/p\u003e\u003c/div\u003e"}},{"title":"输入格式","value":{"format":"HTML","content":"\u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\u003cp\u003e输入含多组数据。\u003c/p\u003e\u003cp\u003e每组数据第一行是两个整数 和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输入以0 0结束。\u003cbr\u003e(n,m\u0026lt;100)\u003c/p\u003e\u003c/div\u003e"}},{"title":"输出格式","value":{"format":"HTML","content":"\u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e对于每组数据输出一行一个整数,即最大收入。\u003c/div\u003e"}},{"title":"样例输入","value":{"format":"HTML","content":"\u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e3 3\u003cbr\u003e\n3 1 2\u003cbr\u003e\n2 3 1\u003cbr\u003e\n1 3 2\u003cbr\u003e\n\u003cbr\u003e\n2 4 3\u003cbr\u003e\n4 3 2\u003cbr\u003e\n3 4 2\u003cbr\u003e\n\u003cbr\u003e\n0 0\u003c/div\u003e"}},{"title":"样例输出","value":{"format":"HTML","content":"\u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e8\u003c/div\u003e"}},{"title":"提示","value":{"format":"HTML","content":"\u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e在样例中,旅行者可以先去城市2,然后去城市1,最后在城市1结束他的旅程。总收入为:\u003cbr\u003e-1+4-2+4-1+4\u003d8。\u003c/div\u003e"}}]}