P11550 [BalticOI 2009] 纪念碑 (Day2)

**译自 [BalticOI 2009](http://www.csc.kth.se/contest/boi/tasks.php) Day2 T3[「Monument」](http://www.csc.kth.se/contest/boi/monument.pdf)** 一位来自瑞典的~~暴发户~~百万富翁想要为她的家人建造一座纪念碑。所有可以追溯到的她的祖先（以及将来的后代）的名字都会被刻在纪念碑上。纪念碑是一个矩形块，顶部和底部是 $a \times a$ 的正方形，高度为 $b$。$a,b$ 的值应该使四个侧面有尽可能多的空间以适应尽可能多的文字。 这座纪念碑将从一个特别的 $p \times q \times r$ 的矩形石块中切割出来，这个石块是由普通石块结晶化而来。也就是说，我们可以把石头看做是由 $1 \times 1 \times 1$ 的单位块组成的，最后的纪念碑也将由这样的单位块组成。原石只能沿着这些单位块之间垂直于 $x,y$ 或 $z$ 轴切割。 原石产生了一些微孔，为空单位块。纪念碑需要精致，所以不允许包含任何微孔（空单位块）。你被给定原石的三维图，它描述了哪些单位块是空的，哪些是正常的。 你的任务是找到满足以下条件的纪念碑： 1. 它可以从原石中切割出来； 2. 纪念碑的四个侧面的面积，即 $4ab$ 要尽量大。

第一行，三个正整数 $p,q$ 和 $r$。 以下 $pq$ 行，每行 $r$ 个字符（和一个换行符，没有多余空格）。 每个字符都是 $\texttt{N}$（正常） 或 $\texttt P$（空）。 第 $1+(yp+x-p)$ 行的第 $z$ 个字符对应原石的单位块 $(x,y,z)$，

一行，$4ab$ 的最大值。

$1 \le x \le p,1 \le y \le q,1 \le z \le r$。 $0\le p,q,r\le 150$。