National Olympiad in Informatics, China, 2013
Little E really likes calligraphy. He heard that NOI2013 has started,
and would like to give a calligraphic design of NOI
to everyone.
Little E has one sheet of magical paper. The paper can be represented as
a two-dimensional grid with rows and columns. We consider the
coordinates of the bottom-left corner to be and the coordinates
of the top-right corner to be . Each cell of the grid contains
an integer "luckiness" value. Writing on a cell can increase everyone's
luckiness. The overall luckiness just happens to be the sum of the
luckiness values across all cells that have been written on. Now, you
need to write the three letters N
, O
, and I
onto the paper.
The three calligraphic letters are defined as follows:
- The
N
is made up of some number of rectangles which are parallel to the grid's axes. Let be the number of rectangles (numbered from to ), then the -th rectangle's bottom-left corner will have coordinates , and its top-right corner will have coordinates . These values will satisfy:- ;
- For all , it will hold true that ;
- For all , it will hold true that ;
- .
- The
O
is made up of a bigger rectangle , with a smaller rectangle carved out of it. The two rectangles both have sides parallel to the grid's axes. Let represent the coordinates of the bottom-left corner of rectangle , and and represent its width and height respectively. Then, the smaller rectangle will have bottom-left corner at , a width of , and a height of . These values will satisfy:- ;
- .
- The
I
is made up of rectangles with sides parallel to the grid's axes, numbered , , and from bottom to top. Let represent the coordinates rectangle 's bottom-left corner, and represent the coordinates of its top-right corner. These values will satisfy:- ;
- ;
- ;
- ;
The following depicts an example of a valid calligraphic design of the
letters N
, O
, and I
.
Also, shapes drawn in the design must not extend beyond the boundaries of the grid. Little E would like to determine the maximum possible luckiness that his design could produce.
Input Specification
The first line of input will contain two positive integers and ,
respectively representing the number of rows and columns in the grid.
The next lines will each contain integers. The -th integer on
line of the input represents the luckiness value of the grid
cell at .
Output Specification
Output a single integer , representing the maximum total luckiness that his design could produce.
Sample Input 1
3 13
1 1 -1 -1 1 -1 1 1 1 -1 1 1 1
1 -1 1 -1 1 -1 1 -1 1 -1 -1 1 -1
1 -1 -1 1 1 -1 1 1 1 -1 1 1 1
Sample Output 1
24
Explanation for Sample 1
Sample Input 2
3 13
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
Sample Output 2
-20
Explanation for Sample 2
The following is one optimal design. There also exist other optimal designs.
Constraints
Test Case | Range of Luckiness Values | ||
---|---|---|---|
All test cases satisfy and .
Problem translated to English by .
Comments