SP3642 PRETTYP - Pretty Printing

一家 IT 公司决定发布内部通讯，介绍成功完成的项目。每个部门提供一段文字，这些文字将被打印在通讯中的指定框内。假设段落仅由字母 a...z 和空格（ASCII 码为 32）组成，且一个单词是指一行中没有空格隔开的最长字符序列。 打印需满足以下条件： - 文字将以等宽字体从左至右打印，并在每行末尾换行。 - 每行打印的字符数量必须一致。 - 单词需要按照它们在段落中的顺序打印，不能拆分或跨多行打印。 - 同一行上的相邻单词之间必须用一个空格隔开。 - 每行只能包括原段落中的单词和空格。 - 如果某行开头是空格，则该行必须全为空格。 编辑希望通过计算段落打印的不平衡度来评估美观程度。不平衡度定义为每行末尾空格数的立方之和（包括全是空格的行）。不平衡度越小，打印效果越美观。 例如，某段落经以下两种方式打印在三行、每行 20 个字符宽度的框内： ``` aaa bbbbbbbbb c dddd eeeeeee ffffff ggggggggg ``` ``` aaa bbbbbbbbb c dddd eeeeeee ffffff ggggggggg ``` 在这个例子中，左侧打印的不平衡度为 $0^3 + 6^3 + 11^3 = 1547$，而右侧为 $7^3 + 6^3 + 4^3 = 623$。显然，右侧的打印更美观。 你的任务是编写一个程序，找出段落在框内打印时的不平衡度最小的方式。

输入包含多个数据集。第一行为一个正整数，表示数据集的数量（不超过 20）。随后是每个数据集的描述。 每个数据集的第一行为整数 $L$（$0 < L \leq 100$），指的是框的行数。第二行为整数 $W$（$0 < W \leq 1000$），表示框的宽度，即每行字符数。之后的若干行为段落，以一个空行结束，段落不超过 1000 个单词。

对于每个数据集，输出一行，表示段落按最美观方式打印时的不平衡度。如果无法在指定框内打印段落，则输出 -1。

- $0 < L \leq 100$ - $0 < W \leq 1000$ - 段落最多包含 1000 个单词。 **本翻译由 AI 自动生成**