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

abcd

edfg

hijk



 

we obtain the table:

acd

efg

hjk



 

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.


-----Input-----

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.


-----Output-----

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


-----Examples-----
Input
1 10
codeforces

Output
0

Input
4 4
case
care
test
code

Output
2

Input
5 4
code
forc
esco
defo
rces

Output
4



-----Note-----

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.

Difficulty: interview

Starter code:

Solutions:
line = input().split()
n = int(line[0])
m = int(line[1])

lst = [input()]
sml = []
for i in range(n - 1):
    lst.append(input())
    sml.append(False)

ans = 0
for i in range(m):
    flag = True
    for j in range(n - 1):
        flag = flag and ((lst[j][i] <= lst[j + 1][i]) or sml[j])
    if flag:
        for j in range(n - 1):
            if lst[j][i] < lst[j + 1][i]:
                sml[j] = True
    else:
        ans += 1

print(str(ans))


def main():
    n, m = list(map(int, input().split()))
    l = [input() for _ in range(n)]
    lead = [[] for _ in range(n)]
    x = 0
    for nn in zip(*l):
        for l, c in zip(lead, nn):
            l.append(c)
        if tuple(l[-1] for l in sorted(lead)) != nn:
            x += 1
            for l in lead:
                del l[-1]
    print(x)


def __starting_point():
    main()

__starting_point()

def kkr():
    n, m= [int(i) for i in input().split()]
    a= []
    for i in range(n):
        a.append([i for i in input()])
    ans= 0
    
    for i in range(m):
        for j in range(n-1):
            if a[j][:i+1]> a[j+1][:i+1]:
                for k in range(n):
                    a[k][i]= "z"
                ans+= 1
                break
    
    print(ans)

kkr()
        


line = input().split()
n = int(line[0])
m = int(line[1])
data = []
for i in range(n):
    data.append(input())
    
x = [1 for i in range(n)]
delete = 0
for i in range(m):
    dum = [1 for j in range(n)]
    status = 1
    for j in range(1,n):
        if data[j][i] > data[j-1][i]:
            dum[j] = 0
        elif data[j][i] == data[j-1][i]:
            dum[j] = 1
        else:
            if x[j] == 1:
                delete += 1
                status = 0
                break
    if status == 1:
        for j in range(len(dum)):
            if dum[j] == 0:
                x[j] = 0
print(delete)


from copy import deepcopy

n, m = list(map(int, input().split()))
words = [input() for _ in range(n)]

i = 1
ans = 0
while True:
    if i > len(words[0]): break
    for j in range(n-1):
        if words[j][:i] > words[j+1][:i]:
            ans += 1
            words = [x[:(i-1)]+x[i:] for x in words]
            i -= 1
            break
    i += 1

print(ans)
        


def sortedx(lst):
    copy = lst[:]
    copy.sort()
    if copy == lst:
        return True
    return False

a, b = list(map(int, input().split(' ')))
words = [input() for i in range(a)]
each = ['' for i in range(a)]

for j in range(b):
    if sortedx([each[i] + words[i][j] for i in range(a)]):
        for ix in range(a):
            each[ix] = each[ix] + words[ix][j]
            

print(b - len(each[0]))




### NOT FINISHED
# I really need to make it go from line to line:
# first, the first 2 lines should be corrected
# then, the third, and so on.

def issorted(l):
    return all(l[i] <= l[i+1] for i in range(len(l)-1))

def mainX(n,m,t):
    ans = 0
    while not issorted(t):
        remove = -1
        for i in range(len(t) - 1):
            if t[i] > t[i+1]:
                for j in range(len(t[i])):
                    if t[i][j] != t[i+1][j]:
                        remove = j
                        break
            if remove != -1:
                print(i,remove)
                break
        t = [_t[:remove] + _t[remove+1:] for _t in t]
        ans += 1
    print(ans)

def is_good(s):
    return all(s[i] <= s[i+1] for i in range(len(s)-1))
def line_is_good(a,j):
    return all(a[i][j] <= a[i+1][j] for i in range(len(a)-1))
def main5(n,m,a):
    if n <= 1 or m<=0 or is_good(a):
        print(0)
        return
    bad = []
    for i in range(0,m):
        if line_is_good(a,i):
            continue
        #if bad == []: bad.append(i)
        s = ["".join([k for b,k in enumerate(x) if b not in bad]) for x in a]
        print(i,bad)
        if is_good(s):
            print(len(bad))
            return
        else:
            bad.append(i)
    print(m)
def main6(n,m,a):
    if n <= 1 or m<=0 or is_good(a):
        print(0)
        return
    bad = []
    good = list(range(m))
    ans = 0
    while not is_good(a):
        remove = -1

    return
    for i in range(0,m):
        if line_is_good(a,i):
            continue
        bad.append(i)
        #print(i)
        s = ["".join([k for b,k in enumerate(x) if b not in bad]) for x in a]
        if is_good(s):
            print(len(bad))
            return
    print(m)

def main(n,m,a):
    if n <= 1 or m<=0 or is_good(a):
        print(0)
        return
    bad = []
    ans = 0
    while not is_good(a):
        remove = -1
        for i in range(n-1):
            if a[i] > a[i+1]:
                for j in range(len(a[i])):
                    if a[i][j] > a[i+1][j]:
                        remove = j
                        break
            if remove != -1:
                break
        a = [x[:remove] + x[remove+1:] for x in a]
        ans += 1
    print(ans)

def main_input():
    n,m = [int(i) for i in input().split()]
    a = [input() for s in range(n)]
    main(n,m,a)

def __starting_point():
    main_input()

__starting_point()

#!/usr/bin/env python3

n, m = list(map(int, input().split()))
words = [input() for _ in range(n)]

i = 1
ans = 0
while True:
    if i > len(words[0]): break
    for j in range(n-1):
        if words[j][:i] > words[j+1][:i]:
            ans += 1
            words = [x[:(i-1)]+x[i:] for x in words]
            i -= 1
            break
    i += 1

print(ans)


#!/usr/bin/env python
#def input(f=open('in3')): return f.readline().rstrip()

n, m = list(map(int, input().split()))
txt = [ input() for _ in range(n) ]
sol = 0

pof = list(range(n-1))
for i in range(m):

    cli = [ rw[i] for rw in txt ]
    of = [x for (x,y) in zip(pof, [i+1 for i in pof])
            if cli[x] > cli[y]]
    if (len(of) > 0):
        sol += 1
        continue

    nf = [x for (x,y) in zip(pof, [i+1 for i in pof])
            if cli[x] < cli[y]]
    pof = [t for t in pof
             if t not in nf]

print(sol)


v=list((input().split()))
n=int(v[0])
m=int(v[1])
v=list()
for i in range(n):
    v.append(input())
if n==1:
    print(0)
    return
kll=0
j=0
brk=0
while j<m:
    for i in range (1,n):
        if v[i][:j+1]<v[i-1][:j+1]:
            brk=1
            break
    if brk:
        for i in range(n):
            tmp=list(v[i])
            tmp.pop(j)
            v[i]="".join(tmp)
        kll+=1
        m-=1
    else:
        j+=1
    brk=0
print(kll)

__author__ = 'trunghieu11 - vuondenthanhcong11@gmail.com'

# ---------- My Tools -------------

# ------ Input output tools -------
def read_int(): return int(input())
def read_ints(): return map(int, input().split())
def read_list_int(): return list(map(int, input().split()))
def read_strings(row_count):
    answer = []
    for i in range(0, row_count): answer.append(input())
    return answer


# ---------- Actual Code ----------

row_count, column_count = read_ints()
table = read_strings(row_count)

save = set()
answer = 0

for j in range(0, column_count):
    isOk = True
    for i in range(1, row_count):
        if table[i][j] < table[i - 1][j] and ((i - 1) << 15 | i) not in save:
            isOk = False
            answer += 1
            break
    if isOk:
        for i in range(1, row_count):
            if table[i][j] > table[i - 1][j]:
                save.add(((i - 1) << 15 | i))

print(answer)

import sys
n, m = [int(i) for i in input().split()]
a = [[0] * n for i in range(m)]
for i in range(n):
    temp = input()
    for j in range(m):
        a[j][i] = temp[j]

c = 0

def blatant(a):
    for i in range(1,len(a)):
        if a[i] < a[i-1]:
            return True
    return False

match = []
while True:
    if len(a) == 0:
        print(m)
        return
    elif blatant(a[0]):
        del a[0]
        c += 1
    else:
        break

for i in range(1,n):
    if a[0][i] == a[0][i-1]:
        match.append(i)
        
def rm(a,match):
    c = 0
    for m in match:
        i = 1
        while i < len(a):
            if a[i][m] < a[i][m-1]:
                del a[i]
                c += 1
            elif a[i][m] == a[i][m-1]:
                i += 1
            else:
                break
    return c

while True:
    temp = rm(a,match)
    if temp == 0:
        break
    c += temp
    
print(c)


n, m = map(int, input().split())
t = [input() for i in range(n)]
p = [''] * n
s = r = 0
for k in range(m):
    b = p[0] + t[0][k]
    for j in range(1, n):
        a, b = b, p[j] + t[j][k]
        if a > b:
            s += 1
            break
    if r < s: r = s
    else:
        for j in range(n): p[j] += t[j][k]
print(s)

def input_split(f): return list(map(f, input().split()))


def main():
    n, m = input_split(int)
    lst = [input()]
    sml = []
    for i in range(n - 1):
        lst.append(input())
        sml.append(False)

    ans = 0
    for i in range(m):
        flag = True
        for j in range(n - 1):
            flag = flag and ((lst[j][i] <= lst[j + 1][i]) or sml[j])
        if flag:
            for j in range(n - 1):
                if lst[j][i] < lst[j + 1][i]:
                    sml[j] = True
        else:
            ans += 1

    print(ans)

def __starting_point():
    main()

__starting_point()

R = input
n, m = map(int, R().split())
N = range(n)
v = zip(*map(list, [R() for _ in N]))
g = [0]*n
s = 0
for r in v:
    if sum(g[i] or r[i]>=r[i-1] for i in N[1:])<n-1:
        s+=1
    else:
        for i in N[1:]:g[i]|=r[i]>r[i-1]
print(s)

def remove(p, a):
	for i in range(len(a)):
		a[i] = a[i][: p] + a[i][p + 1: ]

n, m = [int(x) for x in input().split()]
a = []
for i in range(n):
	a.append(input())
removed = 0
for i in range(m):
	i -= removed
	for j in range(n - 1):
		if a[j][: i + 1] > a[j + 1][: i + 1]:
			remove(i, a)
			removed += 1
			break
print(removed)


def lexyco(table, pos):
    for i in range(len(table)-1):
        for s2 in table[i+1:]:
            if (table[i][:pos+1] > s2[:pos+1]):
                return False
    return True

n, m = map(int, input().split())
table = []
for i in range(n):
    table.append(input())
cnt = 0
i = 0
while i < len(table[0]):
    if lexyco(table, i):
        i += 1
    else:
        cnt += 1
        for s in range(len(table)):
            table[s] = table[s][:i] + table[s][i+1:]
print(cnt)

s = input()
s = s.split()
n = int(s[0]) # Linhas
m = int(s[1]) # Colunas
l = []

for i in range(0,n):
	s = input()
	l.append(s)

cont = 0

ant = 0
i = 0
while (i < n):
	if (l[ant] > l[i]):
		for k in range(0, n):
			l[k] = list(l[k])
		achou = False

		j = 0
		for j in range(0, m):
			if (l[ant][j] > l[i][j]):
				achou = True
				break

		for k in range(0, n):
			l[k].pop(j)
			l[k] = "".join(l[k])

		i = 0
		ant = 0
		m -= 1
		cont += 1

	else: 
		ant = i
		i += 1

print(cont)

s = input()
s = s.split()
n = int(s[0]) # Linhas
m = int(s[1]) # Colunas
l = []

for i in range(0,n):
	s = input()
	l.append(s)

cont = 0

ant = 0
i = 0
while (i < n):
	if (l[ant] > l[i]):
		for k in range(0, n):
			l[k] = list(l[k])

		for j in range(0, m):
			if (l[ant][j] > l[i][j]):
				break

		for k in range(0, n):
			l[k].pop(j)
			l[k] = "".join(l[k])

		i = 0
		ant = 0
		m -= 1
		cont += 1

	else: 
		ant = i
		i += 1

print(cont)

from collections import defaultdict, deque
def main():
    n, m = map(int, input().split())
    a = [[c for c in input()] for i in range(n) ]
    che = [ [0 for i in range(n+2)] for j in range(n+2)]
    ans = 0
    for j in range(m):
        check = False
        for i in range(n-1):
            if a[i][j] > a[i+1][j]:
                if not che[i][i+1]:
                    ans += 1
                    check = True
                    break
        if not check:
            for i in range(n-1):
                if a[i][j] < a[i+1][j]:
                    che[i][i+1] = 1
    print(ans)

def __starting_point():
    main()
__starting_point()

read = lambda: list(map(int, input().split()))
n, m = read()
a = [input() for i in range(n)]
ans = 0
ind = [i for i in range(1, n)]
for i in range(m):
    ind2 = []
    for j in ind:
        if a[j][i] < a[j - 1][i]:
            ans += 1
            break
        elif a[j][i] == a[j - 1][i]:
            ind2.append(j)
    else:
        ind = ind2[:]
print(ans)


# from itertools import combinations
# from bisect import bisect_left
# from functools import *
# from collections import Counter

def is_lexigraphic(s):
  for i in range(len(s) - 1):
    if s[i] > s[i + 1]:
      return False
  return True

I = lambda: list(map(int, input().split()))
n, m = I()
a = [input() for i in range(n)]
mn = m
columns = list(zip(*a))
for i in range(m):
  curCol = columns[i]
  if not is_lexigraphic(curCol):
    continue
  l = []
  for j in range(n - 1):
    if curCol[j] == curCol[j + 1]:
      l.append(j)
  x = 0
  for k in range(i + 1, m):
    if any([columns[k][a] > columns[k][a + 1] for a in l]):
      x += 1
    elif any([columns[k][a] == columns[k][a + 1] for a in l]):
      l = [a for a in l if columns[k][a] == columns[k][a + 1]]
    else:
      break
  mn = min(x + i, mn)
print(mn)

# from itertools import combinations
# from bisect import bisect_left
# from functools import *
# from collections import Counter

I = lambda: list(map(int, input().split()))
n, m = I()
ans = 0
columns = list(zip(*[input() for i in range(n)]))
g = [0 for _ in range(n)]
for column in columns:
  if sum(g[i] or column[i] <= column[i + 1] for i in range(n - 1)) == n - 1:
    for i in range(n - 1):
      g[i] |= column[i] < column[i + 1]
  else:
    ans += 1
print(ans)

def remove(p, a):
	for i in range(len(a)):
		a[i] = a[i][: p] + a[i][p + 1: ]

n, m = [int(x) for x in input().split()]
a = []
for i in range(n):
	a.append(input())
removed = 0
for i in range(m):
	i -= removed
	for j in range(n - 1):
		if a[j][: i + 1] > a[j + 1][: i + 1]:
			remove(i, a)
			removed += 1
			break
print(removed)




# Made By Mostafa_Khaled


n,m=map(int,input().split())
ans=0
st=[input() for i in range(n)]
new=['']*n
for i in range(m):
	newstr=[new[j]+st[j][i] for j in range(n)]
	if(newstr==sorted(newstr)):
		new=newstr
	else:
		ans+=1
print(ans)