{"trustable":false,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cscript type\u003d\u0027text/x-mathjax-config\u0027\u003eMathJax.Hub.Config({tex2jax: { inlineMath: [[\u0027$\u0027,\u0027$\u0027]] } }); \u003c/script\u003e\n\u003cscript type\u003d\u0027text/javascript\u0027 src\u003d\u0027https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\u0027\u003e\u003c/script\u003e\n\u003cscript type\u003d\u0027text/javascript\u0027\u003esetTimeout(function(){MathJax.Hub.Queue([\u0027Typeset\u0027, MathJax.Hub, \u0027left_view\u0027]);}, 2000);\u003c/script\u003e\n\u003cdiv class\u003d\"panel_content\"\u003e\n 众所周知,刘学长是北华村首富,他跟别的富豪不一样,他想要帮助穷人。于是\n他决定派自己的小弟docker去帮助穷人。\ndocker听从刘学长的命令来到一个贫困村庄中。这个村庄是一个n*n户人家形成的\n矩阵。每一户人家都提出他们想要金额。docker一开始在(1,1)的位置,并且已经帮助了这户人家,由于\n跟在刘学长手下、吃香的喝辣的,docker的体能不是特别好。所以他每一次移动,\n都可以选择上下左右四个方向,每次移动距离不超过k。docker每到一户人家\n就必定会满足那户人家的要求,即给予他们想要的金额。docker又一个缺点,\n他每次帮助完一户人家,下一户他帮助的人家就必定比这户穷。即如果下\n一户没有这一户穷,他是不会去的。docker认为,提出的金额需求越多,他越穷\n。当docker能到达的地方没有比他当前在的地方穷的时候,他就会回到北华村。\n刘学长想要知道docker最多能捐献出的金额。\n \u003cbr\u003e \n\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"有多组测试数据\n每组数据的第一行是两个整数,n,k。\n(1\u003c\u003dn\u003c\u003d100),(1\u003c\u003dk\u003c\u003d100)\n当n,k都为-1时为程序结束标志。\n之后n行,每行n个数字,描述村庄里穷人所需求的金额。\n\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"对于每组数据输出一行,一行仅有一个整数,表示docker能发放的金额最大值。\n\u003cbr\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre\u003e3 1\n1 2 5\n10 11 6\n12 12 7\n-1 -1\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003e37\u003c/pre\u003e"}}]}