{"trustable":true,"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":"\u003cdiv class\u003d\"panel_content\"\u003eFatMouse在一个城市里存放了一些奶酪。这个城市可以被视为一个边长为n的正方形网格:每个网格位置都标有(p,q),其中0 \u003c\u003d p \u003c n且0 \u003c\u003d q \u003c n。在每个网格位置,FatMouse都藏有0到100块奶酪。现在他要开始享用他最喜欢的食物。\u003cbr\u003e\u003cbr\u003eFatMouse从位置(0,0)开始。他先吃掉自己所在位置的奶酪,然后可以沿水平或垂直方向跑到另一个位置。问题在于,有一只名为Top Killer的超级猫坐在他的洞旁边,所以每次他最多只能跑k个位置进入洞穴,否则就会被Top Killer抓住。更糟糕的是,每次吃完一个位置的奶酪后,FatMouse就会变得更胖。因此,为了获得足够的能量进行下一次奔跑,他必须跑到一个位置,那里的奶酪块数比当前洞穴的多。\u003cbr\u003e\u003cbr\u003e给定n、k以及每个网格位置上的奶酪块数,计算在无法移动之前FatMouse可以吃到的最大奶酪块数。\u003cbr\u003e\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"有多个测试用例。每个测试用例包括:\u003cbr\u003e\u003cbr\u003e一行包含两个介于1和100之间的整数:n和k\u003cbr\u003en行,每行有n个数字:第一行包含位置(0,0)、(0,1)、...、(0,n-1)处的奶酪块数;下一行包含位置(1,0)、(1,1)、...、(1,n-1)处的奶酪块数,依此类推。\u003cbr\u003e输入以一对-1结束。\u003cbr\u003e"}},{"title":"输出","value":{"format":"HTML","content":"对于每个测试用例,在一行中输出一个整数,表示收集到的奶酪块数。\u003cbr\u003e"}},{"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 1\r\n1 2 5\r\n10 11 6\r\n12 12 7\r\n-1 -1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e37\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}