{"trustable":true,"sections":[{"title":"Description","value":{"format":"MD","content":"In order to better prepare for NOIP2013, several girls from the computer group, LYQ, ZSC, and ZHQ, believe that we not only need a computer room, but also need exercise. So they decided to ask the principal for a piece of extra-curricular sports ground for the computer group. It is said that they are all experts in the computer group, and the principal did not immediately agree to them, but first gave them a mathematical problem and told them: the area of the sports ground you can get is the largest number you can find.\n\nThe principal first gave them a $n\\times n$ matrix. The task is to find the maximum weighted rectangle in the matrix, that is, each element in the matrix has a weight value, defined on the set of integers. Find a rectangle from it, with unlimited size, that has the maximum sum of all the elements it contains. Each element of the matrix belongs to $[-127,127]$, for example\n\n```plain\n 0 –2 –7 0 \n 9 2 –6 2\n-4 1 –4 1 \n-1 8 0 –2\n```\n\nIn the lower left corner:\n\n```plain\n9 2\n-4 1\n-1 8\n```\n\nThe sum is $15$.\n\nThe girls were a bit puzzled, so they asked the computer group\u0027s meticulous HZH and TZY for help in calculating, but unfortunately their answers were different. We can\u0027t be vague about land matters. Can you help calculate the maximum weighted rectangle in the given matrix provided by the principal?"}},{"title":"Input","value":{"format":"MD","content":"The first line: $n$, followed by $n$ rows and $n$ columns of the matrix."}},{"title":"Output","value":{"format":"MD","content":"The sum of the maximum rectangle (submatrix)."}},{"title":"Sample 1","value":{"format":"MD","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\u003e4\n0 -2 -7 0\n 9 2 -6 2\n-4 1 -4 1 \n-1 8 0 -2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e15\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"Hint","value":{"format":"MD","content":"$1 \\leq n\\le 120$"}}]}