The Game of Rocks

Limits: 500ms, 512 MB

Alice and Bob have come up with a new game.

Bob gives Alice a NxM grid that contains N rows and M columns. Each cell of this grid is either empty or it contains a rock. To win this game, Alice has to choose a rectangle with the highest perimeter enclosed by rocks. The sides of this rectangle has to be axis parallel. The rectangle has to enclose a positive area. If there are multiple such rectangles, Alice has to choose one with the maximum area enclosed by the rocks (See the sample I/O for more detail).

This is a companion discussion topic for the original entry at