背景

译自 Northwestern Europe Regional Contest (NWERC) 2021 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$。

9 30
algorithm
contest
eindhoven
icpc
nwerc
programming
regional
reykjavik
ru

3 4
9 5 11 2 
algorithm icpc  programming ru
contest   nwerc regional      
eindhoven       reykjavik  

6 10
aaa
bb
ccccc
ddd
eeeee
fffff

4 2
3 5
aaa ccccc
bb  ddd
    eeeee
    fffff

5 15
pppp
ppppp
pq
pqab
xyzff

2 3
5 2 5
pppp  pq pqab
ppppp    xyzff

提示

【数据规模与约定】

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