Removing Columns

题意翻译

# 题目描述: 给你一个$n$*$m$的小写字符矩阵,你可以选择删除一些列,使得剩下的字符矩阵的每一行的字符串从上到下的字典序非减。 求最少删除多少列 # 输入格式: 第一行输入两个整数n,m 接下来n行每行输入m个字符 # 输出格式: 输出一个整数表示最少删除的列

题目描述

You are given an $ n×m $ rectangular table consisting of lower case English letters. In one operation you can completely remove one column from the table. The remaining parts are combined forming a new table. For example, after removing the second column from the table `<br></br>abcd<br></br>edfg<br></br>hijk<br></br>`we obtain the table: `<br></br>acd<br></br>efg<br></br>hjk<br></br>`A table is called good if its rows are ordered from top to bottom lexicographically, i.e. each row is lexicographically no larger than the following one. Determine the minimum number of operations of removing a column needed to make a given table good.

输入输出格式

输入格式


The first line contains two integers — $ n $ and $ m $ ( $ 1<=n,m<= $ 100). Next $ n $ lines contain $ m $ small English letters each — the characters of the table.

输出格式


Print a single number — the minimum number of columns that you need to remove in order to make the table good.

输入输出样例

输入样例 #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

说明

In the first sample the table is already good. In the second sample you may remove the first and third column. In the third sample you have to remove all the columns (note that the table where all rows are empty is considered good by definition). Let strings $ s $ and $ t $ have equal length. Then, $ s $ is lexicographically larger than $ t $ if they are not equal and the character following the largest common prefix of $ s $ and $ t $ (the prefix may be empty) in $ s $ is alphabetically larger than the corresponding character of $ t $ .