← 返回题目列表

Codeforces · 496/C

C. 删除列

中文机器翻译题面 查看原题

给出一个由小写英文字母组成的 n × m 矩形表格。通过一项操作,您可以从表中完全删除一列。其余部分组合起来形成一个新表。例如,从表中删除第二列后

我们得到表:

如果一个表的行按字典顺序从上到下排序,即每行按字典顺序不大于下一行,则该表被称为良好表。确定使给定表正常运行所需的删除列的最少操作数。

输入

第一行包含两个整数 — n 和 m (1 ≤ n, m ≤ 100)。

接下来的 n 行每行包含 m 个小英文字母 — 表格中的字符。

输出

打印一个数字 - 为了使表格正常显示而需要删除的最少列数。

示例

输入 #1

1 10
codeforces

输出 #1

0

输入 #2

4 4
case
care
test
code

输出 #2

2

输入 #3

5 4
code
forc
esco
defo
rces

输出 #3

4

注意

在第一个示例中,表格已经很好。

在第二个示例中,您可以删除第一列和第三列。

在第三个示例中,您必须删除所有列(请注意,根据定义,所有行均为空的表被认为是好的)。

让字符串 s 和 t 具有相等的长度。那么,如果它们不相等,并且 s 中 s 和 t 的最大公共前缀(前缀可以为空)后面的字符按字母顺序大于 t 的对应字符,则 s 按字典顺序大于 t。