407279: GYM102741 G Letters Among Us

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

G. Letters Among Ustime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Toast is currently a crewmate on the Skeld, and unfortunately, unbeknownst to him, there has been a new task added! He's struggling a lot with this new task, so much so that Toast is a bit suspicious that the imposters might have already claimed a few crewmates. Just as he wants to give up on the task to check out his fellow crewmates, he sees Abe walk up behind him. Obviously, he does not want to fake a task. Help Toast finish his task so he can win the game!

The new task has a grid of $$$n \times m$$$ consisting of lower case English letters. Toast is allowed to remove any column of letters. The goal here is to remove the smallest number of columns required such that after all the removals, the rows are ordered from top to bottom lexicographically. Specifically, any row cannot be lexicographically smaller than a previous one, but it can be equal. Determine the minimum number of columns required to be removed to make this the case. Note that it may be the case that every column needs to be removed.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ $$$(1 \le n, m \le 10^2)$$$.

The next $$$n$$$ lines each contain $$$m$$$ lowercase English letters, which are the characters in the grid.

Output

A single integer detailing the minimum number of columns that need to be removed.

ExampleInput
2 3
med
bay
Output
2

加入题单

上一题 下一题 算法标签: