Harold has been misbehaving and now his teacher has given him detention! The teacher has written numbers in their binary representation on the chalkboard. These binary numbers are all written with exactly bits (leading zeroes are allowed) and are written in a list. The teacher tells Harold,
You can leave once the -bit binary numbers are sorted from least to greatest.
Harold, being mischievous, decides that as long as there are -bit binary numbers in sorted order, then he is done, even if they are not the original numbers. He will change some of the characters so that the resulting numbers are sorted. He can only change
0s. He is not allowed to add more characters or delete existing characters.
Harold is also lazy, so he wants to change as few characters as possible. Help him find the least number of changes he needs.
Subtask 1 [40%]
Subtask 2 [60%]
The first line contains two space-separated integers, and .
Lines each contain a single string of exactly characters, either
1. The string on line represents the number in the list.
Output a single integer, the minimum number of changes required to sort the list.
Sample Input 1
4 3 111 110 000 100
Sample Output 1
Explanation for Sample 1
Harold can change the first character of the first number, the second character of the second number, and the first character of the third number to get the sorted list.
011 100 100 100
Sample Input 2
10 5 10010 11101 01011 01000 11100 00110 00110 10001 01101 01000
Sample Output 2