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
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 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
Subtask 1 (15%) n,c<=7
Subtask 2 (30%) n,c<=100
Subtask 3 (55%) n,c<=5000
Input
5 3 11100 00011 11111Output
0
You don't need to make a switch, just use configuration 3 throughout
Input
5 5 10000 01000 00100 00010 00001Output
4
Start from config 0, change to config 1, change to config 2, etc. Each of them takes 1 time because they are adjacent
| Subtask | Score |
|---|---|
| 1 | 15 |
| 2 | 30 |
| 3 | 55 |
| 4 | 0 |