Harold has been misbehaving and now his teacher has given him detention! The teacher has written
You can leave once the
-bit binary numbers are sorted from least to greatest.
Harold, being mischievous, decides that as long as there are 0
s to 1
s and 1
s to 0
s. 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.
Constraints
Subtask 1 [40%]
Subtask 2 [60%]
Input Specification
The first line contains two space-separated integers,
Lines 0
or 1
. The string on line
Output Specification
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
3
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
10
Comments