P7741 [AHOI2007] Stone Tile Floor

Xiao Keke arrives in the main hall of a palace. The floor of the hall is made of square stone tiles of the same size. These tiles are colored black or white, forming an $m \times n$ rectangle. Under one of the tiles there is a passage leading to the treasure vault. Xiao Keke cannot try the tiles one by one, because some tiles have traps installed: touching them will trigger the mechanism and cause the entire palace to collapse. According to the treasure map, the passage is within a specific area. This area is a small rectangle with non-zero area, made up of several tiles, and its four sides are parallel to the edges of the hall floor. If we consider all possible rectangles in the floor, then among all rectangles, this area has the maximum value of “number of black tiles minus number of white tiles”. Xiao Keke wants to split the work with you: he will choose the area, and you will compute the difference $S$ between the numbers of black and white tiles. This way, the area containing the passage can be confirmed quickly and accurately. The treasure map says that none of the tiles in this area have traps installed, so once the area is determined, the passage will definitely be found. The treasure is right ahead, so good luck. (Assume that $1$ represents a black tile, and $0$ represents a white tile.)

The first line of the input file contains two integers $m, n$. The next $m$ lines each contain $n$ characters. Each character is either $0$ or $1$.

Output only one number, which is the maximum value of $S$ (as described above) among all possible areas. Output this value.

For $50\%$ of the testdata: $1 \le m, n \le 200$. For $100\%$ of the testdata: $1 \le m, n \le 400$. Translated by ChatGPT 5