Problem Description
Desmond the Moon Bear has a scanner :O
He wants to scan through a couple of items
The items must be scanned IN ORDER with the first item being scanned first, then the second item and so on...
However, the scanner comes with a few configurations. In the current configuration, only some items may be scanned
Configurations can be switched, but such a switch is very costly and takes time
In fact, switching from configuration i to j takes abs(i-j) time
Help Desmond find the minimum amount of time required to scan through all the items
Input
The first line of the input contains two integers, n and c, the number of items to be scanned and the number of different configurations
Each subsequent c lines of the input contains of a string of n 0s and 1s. A 0 on line i (starting from 2nd line) on column j (both 0-indexed) indicates the item j cannot be read by configuration i, a 1 indicates that item j can be read by configuration i
Output
Output the minimum amount of time taken to scan all of the items
You are guaranteed there is at least one possible way to scan all of the items
Subtasks
Subtask 1 (15%) n,c<=7
Subtask 2 (30%) n,c<=100
Subtask 3 (55%) n,c<=5000
Sample Testcase 1
Input
5 3
11100
00011
11111
Output
0
Explanation
You don't need to make a switch, just use configuration 3 throughout
Sample Testcase 2
Input
5 5
10000
01000
00100
00010
00001
Output
4
Explanation
Start from config 0, change to config 1, change to config 2, etc. Each of them takes 1 time because they are adjacent