#K83487. Maximum Rectangle of Weeds

    ID: 36208 Type: Default 1000ms 256MiB

Maximum Rectangle of Weeds

Maximum Rectangle of Weeds

You are given a rectangular grid representing a farm field. Each cell in the grid is either a weed ('W') or a crop ('C'). Your task is to find the area of the largest rectangle that contains only weeds ('W') in the grid.

The rectangle must be contiguous and its sides must be parallel to the grid axes.

Note: If there are no weeds in the grid, the answer is 0.

Example:

Input:
4
CCCCWCCCC
WWWWWCCCC
WWWWWCCCC
CCCCCCCCW

Output: 10

</p>

The above example corresponds to a grid of 4 rows, and the maximum rectangle of 'W' has an area of 10.

inputFormat

The input is read from standard input (stdin) and has the following format:

  • The first line contains an integer n, the number of rows in the grid.
  • The following n lines each contain a string representing a row of the grid. Each character in the string is either 'W' (weed) or 'C' (crop).

outputFormat

Print a single integer to standard output (stdout) which is the area of the largest rectangle containing only 'W'.

## sample
4
CCCCWCCCC
WWWWWCCCC
WWWWWCCCC
CCCCCCCCW
10

</p>