{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\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 type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eSummer is coming! It\u0027s time for Iahub and Iahubina to work out, as they both want to look hot at the beach. The gym where they go is a matrix \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003c/span\u003e with \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e lines and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e columns. Let number \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e[\u003ci\u003ei\u003c/i\u003e][\u003ci\u003ej\u003c/i\u003e]\u003c/span\u003e represents the calories burned by performing workout at the cell of gym in the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th line and the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/span\u003e-th column.\u003c/p\u003e\u003cp\u003eIahub starts with workout located at line \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e and column \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e. He needs to finish with workout \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e[\u003ci\u003en\u003c/i\u003e][\u003ci\u003em\u003c/i\u003e]\u003c/span\u003e. After finishing workout \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e[\u003ci\u003ei\u003c/i\u003e][\u003ci\u003ej\u003c/i\u003e]\u003c/span\u003e, he can go to workout \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e[\u003ci\u003ei\u003c/i\u003e + 1][\u003ci\u003ej\u003c/i\u003e]\u003c/span\u003e or \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e[\u003ci\u003ei\u003c/i\u003e][\u003ci\u003ej\u003c/i\u003e + 1]\u003c/span\u003e. Similarly, Iahubina starts with workout \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e[\u003ci\u003en\u003c/i\u003e][1]\u003c/span\u003e and she needs to finish with workout \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e[1][\u003ci\u003em\u003c/i\u003e]\u003c/span\u003e. After finishing workout from cell \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e[\u003ci\u003ei\u003c/i\u003e][\u003ci\u003ej\u003c/i\u003e]\u003c/span\u003e, she goes to either \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e[\u003ci\u003ei\u003c/i\u003e][\u003ci\u003ej\u003c/i\u003e + 1]\u003c/span\u003e or \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e[\u003ci\u003ei\u003c/i\u003e - 1][\u003ci\u003ej\u003c/i\u003e]\u003c/span\u003e. \u003c/p\u003e\u003cp\u003eThere is one additional condition for their training. They have to meet in exactly one cell of gym. At that cell, none of them will work out. They will talk about fast exponentiation (pretty odd small talk) and then both of them will move to the next workout.\u003c/p\u003e\u003cp\u003eIf a workout was done by either Iahub or Iahubina, it counts as total gain. Please plan a workout for Iahub and Iahubina such as total gain to be as big as possible. Note, that Iahub and Iahubina can perform workouts with different speed, so the number of cells that they use to reach meet cell may differs.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line of the input contains two integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e3 ≤ \u003ci\u003en\u003c/i\u003e, \u003ci\u003em\u003c/i\u003e ≤ 1000\u003c/span\u003e). Each of the next \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e lines contains \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e integers: \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/span\u003e-th number from \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th line denotes element \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e[\u003ci\u003ei\u003c/i\u003e][\u003ci\u003ej\u003c/i\u003e]\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e0 ≤ \u003ci\u003ea\u003c/i\u003e[\u003ci\u003ei\u003c/i\u003e][\u003ci\u003ej\u003c/i\u003e] ≤ 10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e\u003c/span\u003e).\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eThe output contains a single number — the maximum total gain possible. \u003c/p\u003e"}},{"title":"Examples","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 3\n100 100 100\n100 1 100\n100 100 100\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e800\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIahub will choose exercises \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e[1][1] → \u003ci\u003ea\u003c/i\u003e[1][2] → \u003ci\u003ea\u003c/i\u003e[2][2] → \u003ci\u003ea\u003c/i\u003e[3][2] → \u003ci\u003ea\u003c/i\u003e[3][3]\u003c/span\u003e. Iahubina will choose exercises \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e[3][1] → \u003ci\u003ea\u003c/i\u003e[2][1] → \u003ci\u003ea\u003c/i\u003e[2][2] → \u003ci\u003ea\u003c/i\u003e[2][3] → \u003ci\u003ea\u003c/i\u003e[1][3]\u003c/span\u003e.\u003c/p\u003e"}}]}