{"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":"\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/c9a0bd0fb5e639a8ebfff99b64816545?v\u003d1715369030\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e\u003cp\u003ePor Costel has discovered a writing from porcine mythology: \"The Ballad of the Pig\". The ballad describes a love story between a boar and a gilt. In one of the chapters, the boar tries to impress his significant other by erecting a pig pen. He fails, being tragically limited by his porcine nature. But then the ballad continues saying that the pig eventually found a fabulous orchard in the middle of a forest which he took as a home for himself and the gilt.\u003c/p\u003e\u003cp\u003ePor Costel is, however, not impressed by either forced rhymes, or exaggerated figurative speech. \"A forest is full of orchards\" he says. \"It\u0027s just a matter of how you choose it\".\u003c/p\u003e\u003cp\u003eYou are provided with an \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/991f81a208dc8412840eaec877974cb3?v\u003d1715369030\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003ex\u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/9dc9e70dcd6afa4c4d226e8f165ad0f0?v\u003d1715369030\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e matrix which describes a \"forest\". Each cell has an integer value - the degree of its beauty. You are tasked with choosing an \"orchard\", meaning a subset of cells that satisfies the following conditions:\u003c/p\u003e\u003cul\u003e \u003cli\u003e It is non-empty \u003c/li\u003e\u003cli\u003e It is connected(you can get from any cell to any other cell by passing only through cells that have a common side) \u003c/li\u003e\u003cli\u003e The intersection of the subset with any row of the matrix is either empty, or a connected(the same of definition as above) subset of cells. In other words, on each row, the subset should have either no cell, or a continuous interval of cells. \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eThe beauty of an orchard is defined as the sum of its cells\u0027 beauty degrees. Out of all orchards, pick the one with maximum beauty\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe input \u003cspan class\u003d\"tex-font-style-bf\"\u003elivada2.in\u003c/span\u003e will contain on the first line \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/bfd224968ce516f58bc4320c2b68776f?v\u003d1715369030\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e (\u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/c27a0508694334ebbb06a1db8cc4778b?v\u003d1715369030\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e), the number of tests.\u003c/p\u003e\u003cp\u003eEach of the \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/bfd224968ce516f58bc4320c2b68776f?v\u003d1715369030\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e tests has the following format: on the first line there will be two natural numbers \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/991f81a208dc8412840eaec877974cb3?v\u003d1715369030\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e and \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/9dc9e70dcd6afa4c4d226e8f165ad0f0?v\u003d1715369030\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e, the number of rows and the number of columns of the matrix (\u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/33b29908e341ca9225e2a36940846dec?v\u003d1715369030\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e). \u003c/p\u003e\u003cp\u003eEach of the next \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/991f81a208dc8412840eaec877974cb3?v\u003d1715369030\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e lines will contain \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/9dc9e70dcd6afa4c4d226e8f165ad0f0?v\u003d1715369030\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e integers separated by spaces. The \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/6c8d8037e3a9f2455b5d905d87321c6c?v\u003d1715369030\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e-th number of the \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/00fe2f3abc32471332aa4477c66d0911?v\u003d1715369030\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e-th line will be \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/cc2b36c64f46adcc3da84b98114a443d?v\u003d1715369030\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e the beauty degree of cell \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/42329a5af0da6a575d84607deb1c8178?v\u003d1715369030\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e (\u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/883c941a4aa32967acfe44079f534643?v\u003d1715369030\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eThe output file \u003cspan class\u003d\"tex-font-style-bf\"\u003elivada2.out\u003c/span\u003e will contain \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/bfd224968ce516f58bc4320c2b68776f?v\u003d1715369030\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e lines and each of these lines will contain a single integer number, the maximum beauty of an orchard.\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\u003e1\n3 4\n5 -3 0 0\n-2 3 3 4\n-7 -6 4 -5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e17\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}