{"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\"\u003e绝望平原曾经是一个古老的战场,那里的勇敢灵魂已经安息了数千年。实际上,直到“平原下面有一个巨大的金矿”这个传言开始传播之前,没有人敢踏入这片圣地。\u003cbr\u003e\u003cbr\u003e最近,一场事故摧毁了永恒的宁静。一些贪婪的愚蠢之徒试图使用强大的炸弹来寻找隐藏的宝藏。当然他们失败了,这种行为激怒了那些灵魂--后果是附近所有的人类村庄都被鬼魂所困扰。\u003cbr\u003e\u003cbr\u003e为了尽快制止这些鬼魂,大法师熊猫和伟大的建筑师费瑟想出了一个好计划。由于平原可以表示为N行M列的网格,计划是我们在每一行中选择一个单元格来建造一个魔法塔,这样每个塔都可以使用神圣之光来保护整个行,最终整个平原都可以被覆盖,所有灵魂都可以再次安息。在每个行中建造一个魔法塔的总时间最小化是目标。\u003cbr\u003e\u003cbr\u003e“啊,我们可能会遇到一些困难。”熊猫说,“为了正确控制这些塔,我们必须保证每两个相邻行中的塔共享一个公共的魔法区域。”\u003cbr\u003e\u003cbr\u003e“什么?”\u003cbr\u003e\u003cbr\u003e“具体来说,如果我们在单元格(i,j)和单元格(i+1,k)中建造一个塔,那么我们必须保证|j-k|≤f(i,j)+f(i+1,k)。这里,f(i,j)表示单元格(i,j)中的魔法流量的规模。”\u003cbr\u003e\u003cbr\u003e“怎么做?”\u003cbr\u003e\u003cbr\u003e“呃,我忘了你不能感知魔法力量。这是一个显示每个单元格中魔法流量规模的地图。记住,这个约束对于每两个相邻的行都成立。”\u003cbr\u003e\u003cbr\u003e“明白了。”\u003cbr\u003e\u003cbr\u003e“太棒了!让我们开始吧!”\u003cbr\u003e\u003cbr\u003e你介意帮助他们吗?\u003cbr\u003e\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"有多个测试用例。\u003cbr\u003e\u003cbr\u003e每个测试用例以包含2个整数N和M的一行开始(2≤N≤100,1≤M≤5000),表示平原由N行M列组成。\u003cbr\u003e\u003cbr\u003e接下来的N行包含每行M个整数,形成一个N×M的矩阵T。第i行中第j个元素(Tij)表示在单元格(i, j)中建造魔法塔的时间成本。(0≤Tij≤100000)\u003cbr\u003e\u003cbr\u003e接下来的N行包含每行M个整数,形成一个N×M的矩阵F。第i行中第j个元素(Fij)表示在单元格(i, j)中魔法流量的规模。(0≤Fij≤100000)\u003cbr\u003e\u003cbr\u003e对于每个测试用例,总是存在满足约束条件的解。\u003cbr\u003e\u003cbr\u003e输入以N\u003d0且M\u003d0的测试用例结束。\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 5\r\n9 5 3 8 7\r\n8 2 6 8 9\r\n1 9 7 8 6\r\n0 1 0 1 2\r\n1 0 2 1 1\r\n0 2 1 0 2\r\n0 0\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e10\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}