Вам дана прямоугольная таблица размера n × m, состоящая из маленьких латинских букв. За одну операцию можно целиком удалить из таблицы один столбец; оставшиеся части образуют новую сплошную таблицу. Например, после удаления второго столбца из таблицы
abcd
edfg
hijk
получится таблица:
acd
efg
hjk
Таблица называется хорошей, если ее строки упорядочены сверху вниз в лексикографическом порядке, т.е. каждая строка лексикографически не превосходит следующую за ней. Определите минимальное количество операций удаления столбца, необходимых для того, что сделать данную таблицу хорошей.
Выходные данные
Выведите одно число — минимальное число столбцов, которые необходимо удалить, чтобы таблица стала хорошей.
Примечание
В первом примере таблица уже является хорошей.
Во втором примере достаточно удалить первый и третий столбец.
В третьем примере необходимо удалить все столбцы (обратите внимание, что таблица, в которой все строки пустые, по определению является хорошей).
Пусть строки s и t имеют равную длину. Тогда строка s лексикографически больше строки t, если они не совпадают, и следующий за максимальным общим префиксом s и t (общий префикс может быть пустым) символ строки s идет в алфавитном порядке позже соответствующего символа строки t.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 10
codeforces
|
0
|
|
2
|
4 4
case
care
test
code
|
2
|
|
3
|
5 4
code
forc
esco
defo
rces
|
4
|