{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cp\u003ePirate Dick finally had enough of fighting, marauding,\n theft, and making life miserable for many on the open seas. So\n he decided to retire, and he found the perfect island to spend\n the rest of his days on, provided he does not run out of money.\n He has plenty of gold coins now, and he wants to store them in\n a chest (he is a pirate after all). Dick can construct a\n rectangular chest with integer dimensions of any size up to a\n specified maximum size for the top but with an arbitrary\n integer height. Now he needs a place to hide the chest. While\n exploring the island, he found the perfect solution.\u003c/p\u003e\n\n \u003cp\u003eDick will hide his chest by submerging it in a murky pond.\n The pond has a rectangular surface, and it completely fills the\n bottom of a valley that has high vertical rocky walls. Dick\n surveyed the pond and knows its depth for each of the squares\n of a Cartesian coordinate grid system placed on the pond\n surface. When Dick submerges the chest, it will sink as far as\n possible until it touches the bottom. The top of the chest will\n remain parallel to the pond’s surface and the chest will be\n aligned with the grid squares. The water displaced by the\n submerged chest will raise the level of the pond’s surface\n (this will occur even if there is no space around the chest for\n the displaced water to rise). The walls of the valley are high\n enough that the water can never splash out of the valley. Of\n course, since the chest must be invisible, its top must be\n strictly below the surface of the pond. Your job is to find the\n volume of the largest chest that Pirate Dick can hide this\n way.\u003c/p\u003e\n\n \u003cp\u003eIn Figure\u0026nbsp;1, the leftmost image shows a pond, the\n middle image shows a possible placement of a chest of volume 3,\n and the rightmost image shows a placement of a chest of volume\n 4, which is the maximum possible volume. Note that if the\n second chest were made one unit taller, its top would be\n visible because it would be at exactly the same height as the\n surface of the water.\u003c/p\u003e\n\n \u003cdiv id\u003d\"fig:pirate\" class\u003d\"figure\"\u003e\n \u003ccenter\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/2fad9190b4aaebf30944b41af9d16a07?v\u003d1715444990\" alt\u003d\"\\includegraphics[width\u003d0.75\\textwidth ]{pirate}\" style\u003d\"width:75.00%\"\u003e\n\n \u003cdiv class\u003d\"caption\"\u003e\n \u003cb\u003eFigure 1\u003c/b\u003e: Illustration of Sample Input 1.\n \u003c/div\u003e\n \u003c/center\u003e\n \u003c/div\u003e\n\n \u003ch2\u003eInput\u003c/h2\u003e\n\n \u003cp\u003eThe input consists of a single test case. A test case starts\n with a line containing four integers \u003cspan class\u003d\"tex2jax_process\"\u003e$a$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$b$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e, and \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1\n \\leq a, b, m, n \\leq 500$\u003c/span\u003e). The pond’s surface\n dimensions are \u003cspan class\u003d\"tex2jax_process\"\u003e$m \\times\n n$\u003c/span\u003e and the maximum size of the top (and bottom) of the\n chest is \u003cspan class\u003d\"tex2jax_process\"\u003e$a \\times b$\u003c/span\u003e. In\n addition, \u003cspan class\u003d\"tex2jax_process\"\u003e$a$\u003c/span\u003e and\n \u003cspan class\u003d\"tex2jax_process\"\u003e$b$\u003c/span\u003e are small enough that\n it is not possible to cover the entire pond with a chest with\n top size \u003cspan class\u003d\"tex2jax_process\"\u003e$a \\times b$\u003c/span\u003e.\n Each of the remaining \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e\n lines in a test case contains \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e integers \u003cspan class\u003d\"tex2jax_process\"\u003e$d_{i,j}$\u003c/span\u003e specifying the pond’s depth\n at grid square \u003cspan class\u003d\"tex2jax_process\"\u003e$(i,j)$\u003c/span\u003e,\n where \u003cspan class\u003d\"tex2jax_process\"\u003e$0 \\leq d_{i,j} \\leq\n 10^9$\u003c/span\u003e for each \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq i\n \\leq m$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq j \\leq\n n$\u003c/span\u003e.\u003c/p\u003e\n\n \u003ch2\u003eOutput\u003c/h2\u003e\n\n \u003cp\u003eDisplay the maximum volume of a rectangular chest with\n integer dimensions (where one of the dimensions of the top is\n bounded by \u003cspan class\u003d\"tex2jax_process\"\u003e$a$\u003c/span\u003e and the\n other is bounded by \u003cspan class\u003d\"tex2jax_process\"\u003e$b$\u003c/span\u003e)\n that can be completely submerged below the surface of the pond.\n If no chest can be hidden in the pond, display \u003ctt class\u003d\"ttfamily\"\u003e0\u003c/tt\u003e.\u003c/p\u003e\n\n \u003ch2\u003eSample 1\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\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 2 3\n2 1 1\n2 2 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n\n \u003ch2\u003eSample 2\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\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\u003e4 1 1 5\n2 0 2 2 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e12\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n\n \u003ch2\u003eSample 3\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\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 3 3 5\n2 2 2 2 2\n2 2 2 2 2\n2 2 2 2 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e18\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}