2009 Baltic Olympiad in Informatics

Day 2, Problem 3: Monument

A Swedish millionaire wants to build a monument for her family. The names of all of her known ancestors (and later, her future descendants) will be inscribed to the sides of the monument. The form of the monument will be a rectangular block with a × a bottom/top squares and height b. That is, the bottom and top of the block will be a × a squares, and each of the four sides of the monument is an a × b rectangle. The values of a and b should be such that the four sides have as much space as possible, in order to fit as many names as possible.

The monument will be cut from a very special p × q × r rectangular stone block that has been crystallised in a regular cubic form. That is, we may view the stone as being composed of 1 × 1 × 1 unit blocks (unit cubes). Also the final monument will be composed of such unit cubes. The raw stone may only be cut perpendicular to the x-, y- or z-axis, along the borders between unit cubes.

The raw stone contains pores, in the form of empty unit cubes. The monument is required to be of high quality and is thus not allowed to contain any pores (empty unit cubes). You are given a 3D-map of the raw stone. The map describes which unit cubes are normal and which empty. Your task is to find such values for the size parameters a and b of the monument that

1. it is possible to cut the monument out of the supplied raw stone block, and
2. the monument contains maximal amount of space on its four sides, that is, the value 4ab is as large as possible.

Input

The input is read from standard input. The first line contains three positive integers separated by single space characters: the values p, q and r (1 ≤ p, q, r ≤ 150). This is followed by pq lines, each of which contains r characters (and a new line character, no other white space). Each of the r characters is either N (normal) or P (pore). The zth character on line 1 + (yp + x - p) corresponds to the unit cube with coordinates (x, y, z) within the raw stone, where 1 ≤ x ≤ p, 1 ≤ y ≤ q and 1 ≤ z ≤ r.

Output

The program should write one line to standard output containing the maximal value of 4ab.

Sample Input

3 2 5
PNNNN
PNNNN
NPPNP
PNNNP
NNNNP
PPNNP

Sample Output

24

All Submissions
Best Solutions

Point Value: 20 (partial)
Time Limit: 6.00s
Memory Limit: 64M
Added: Jul 09, 2010

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

None of the dimensions are privileged --- you want to cut a square prism out of the block, but its orientation is irrelevant as long as you maximize the area of the rectangular face.