{"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\"\u003eOne day, Resty comes to an incredible world to seek Eve -- The origin of life. Lilith, the sister of Eve, comes with him. Although Resty wants to find Eve as soon as possible, Lilith likes to play games so much that you can\u0027t make her make any move if you don\u0027t play with her.\u003cbr\u003e\u003cbr\u003eNow they comes to the magical world and Lilish ask Resty to play with her.\u003cbr\u003e\u003cbr\u003eThe game is following :\u003cbr\u003eNow the world is divided into a m * n grids by Lilith, and Lilith gives each grid a score.\u003cbr\u003eSo we can use a matrix to describe it.\u003cbr\u003eYou should come from cell(0, 0) to cell(m-1, n-1) (Up-Left to Down-Right) and try to colloct as more score as possible.\u003cbr\u003eAccording to Lilish\u0027s rule, you can\u0027t arrive at each cell more than once.\u003cbr\u003e\u003cbr\u003eResty knows that Lilish will be easy to find the max score, and he doesn\u0027t want to lose the game.\u003cbr\u003eSo he want to find the game plan to reach the max score.\u003cbr\u003e\u003cbr\u003eYour task is to calculate the max score that Lilish will find, the map is so small so it shouldn\u0027t be difficult for you, right?\u003cbr\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The input consists of more than one testdata.\u003cbr\u003eProcess to the END OF DATA.\u003cbr\u003eFor each test data :\u003cbr\u003ethe first live give m and n. (1\u0026lt;\u003dm\u0026lt;\u003d8, 1\u0026lt;\u003dn\u0026lt;\u003d9)\u003cbr\u003efollowing m lines, each contain n number to give you the m*n matrix.\u003cbr\u003eeach number in the matrix is between -2000 and 2000"}},{"title":"Output","value":{"format":"HTML","content":"Output Format is \"Case ID: ANS\" one line for each data\u003cbr\u003eDon\u0027t print any empty line to the output"}},{"title":"Sample","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\u003e2 2\r\n1 2\r\n3 1\r\n3 3\r\n0 -20 100\r\n1 -20 -20\r\n1 1 1\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 5\r\nCase 2: 61\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}