Largest L Shape

Time limit2sMemory limit128 MB

Summary
Given a binary grid, find the maximum-area L-shape (union of two rectangles sharing a lower-left corner, wider base and taller top) made entirely of 1-cells.
Level

Medium6 of 10

Topics
Dynamic programming, Matrix, Brute force
Solved
No attempts yet

Problem

A picture made of 0s and 1s is drawn on an n x m grid. You may use only cells whose value is 1 to form an L shape.

In this problem, an L shape is the union of two axis-aligned rectangles that share the same lower-left corner. The lower rectangle must be wider than the upper rectangle, and the upper rectangle must be taller than the lower rectangle. Rotations and reflections of the L shape are not considered, and a plain rectangle is not an L shape.

Find the largest possible area of an L shape contained in the picture and output that area. The input contains at least one valid L shape.

Input

The first line contains two integers n and m. Each of the next n lines contains a string of length m. Every character is either 0 or 1.

Output

Print the maximum area of an L shape that can be formed.

Constraints

  • 1 <= n, m <= 150

Examples1

  1. Example 1

    Input
    9 7
1101111
0111111
1110001
1111111
0110101
1111111
1111111
0111110
1101011
    Expected output
    23