P17043 [NWERC 2021] 术语表排列 / Glossary Arrangement

译自 [Northwestern Europe Regional Contest (NWERC) 2021](http://2021.nwerc.eu) Problem G。 原题许可协议为 CC BY-SA。

在基于 Unix 的操作系统中，最常用的命令之一是 `ls`，它会按字典序显示某个目录中的所有文件列表。在最基本的形式中，`ls` 会将每个文件名单独打印在一行；但为了提高可读性并节省屏幕空间，列表通常会被分成多列并并排显示。 你的一位朋友正在写一本关于 NWERC 的书，并让你负责编辑每章末尾相关术语的术语表。每个术语表都必须使用和 `ls` 相同的多列布局，所以你选择了偷懒的办法：对于术语表中的每个单词，你创建一个以该单词命名的空文件，然后直接让 `ls` 完成繁重工作。 不幸的是，你的朋友并不满意你的排版，并抱怨其中一些排版占用了太多竖向空间。你的方法的问题在于：`ls` 总是形成等高的列，只有最后一列可能较短。有时，如果允许更自由地选择每一列的高度，就可以使用更少的行数： :::align{center}  ::: 图示：使用可变列高可以节省两行。 你不情愿地决定编写自己的改进版 `ls`，即 `ls--`。它同样按字典序显示目录内容，但会使用可变列高，以始终达到最少行数。 每一列有固定宽度，等于该列中最长文件名的长度；相邻列之间用一个空格分隔。每列中的名称必须左对齐，并用空格填充到该列宽度。此外，你正在使用的终端宽度固定为 $w$ 个字符，表格不能超过这个宽度。 给定一个目录内容列表，即若干文件名，请找到一种最优列布局，使打印整个列表所需的行数最少。

输入包含： - 一行两个整数 $n$ 和 $w$（$1 \leq n,w \leq 5\,000$），分别表示文件数量和终端宽度。 - 接下来 $n$ 行，每行一个文件名 $s$（$1 \leq |s| \leq w$，$s$ 只包含小写英文字母）。 文件名互不相同，且已按字典序给出。所有文件名的总字母数不超过 $10^6$。

输出一种列出给定文件名的最优方式： - 第一行输出两个整数 $r$ 和 $c$，表示使用的行数和列数。 - 第二行输出 $c$ 个正整数 $a_1,a_2,\ldots,a_c$，表示各列宽度。 - 然后输出文件名表格，需满足以下格式规则： - 有 $c$ 列，其中第 $i$ 列宽度为 $a_i$；每列中最多有 $r$ 个文件名，这些文件名左对齐并集中在该列顶部。 - 文件名使用空格对齐，列与列之间恰好有一个空格。 - 表格总宽度最多为 $w$。 - 按列从上到下、从左到右读取时，文件名必须按字典序出现。 注意，与其他题目不同，你必须严格遵守上述空白字符格式规则。不过，我们仍允许每行末尾出现尾随空格，即使这些尾随空格使该行超过宽度 $w$。

【数据规模与约定】 对于所有数据，$1 \leq n,w \leq 5\,000$；$1 \leq |s| \leq w$；文件名只包含小写英文字母，互不相同，并且按字典序给出；所有文件名总长度不超过 $10^6$；输出格式对空白字符敏感。