P1653. 压缩贴纸

题目描述

贴纸上的文本由由大小写拉丁字母组成的单词构成。单词由空格、换行符和/或以下标点符号分隔： $,$ 、 $.$ 、 $!$ 、 $?$ 。

每个单词前后可能有任意数量的空格和空行，但每个单词后最多有一个标点符号。贴纸使用等宽字体打印，因此每个字符在纸上占据固定大小的矩形区域。贴纸本身是包围文本的最小矩形，周围有一个字符宽度的边距。

需要打印许多份贴纸，为了最小化纸张消耗，应使贴纸的面积尽可能小。例如，考虑以下文本的贴纸：
Our pink elephants have great size and a small price. Buy our elephants!

若在一行中打印，此贴纸的面积为 $(72 + 2) \times (1 + 2) = 222$ 个字符单位。另一方面，若按四行打印，如下所示：

....................  
.Our.pink.elephants.  
.have.great.size....  
.and.a.small.price..  
.Buy.our.elephants!.  
....................

则贴纸仅需 $(18 + 2) \times (4 + 2) = 120$ 个字符单位。

你的任务是，给定贴纸的文本，将其断行以使得贴纸的面积最小。换行可在任意单词或标点符号后插入，但不能在标点符号前插入。同一行中，每个单词必须与前一个单词或标点用一个空格分隔。你无需保留输入中的其他空格或换行符。

输入包含一行或多行贴纸文本。第一行是一个整数，表示后续的行数。文本仅包含以下字符： $A$ 到 $Z$ 、 $a$ 到 $z$ 、 $,$ 、 $.$ 、 $!$ 、 $?$ 、空格和换行符。文本长度不超过10000个字符。文本中至少包含一个非空格字符，且第一个非空格字符始终是字母。

输出必须包含一个整数，表示最小贴纸的面积。

Our     pink  
Elephants  
have great size and a  
   small  price    .  
      Buy our elephants !

Northeastern Europe 2001, Far-Eastern Subregion