scanner

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


Submitting .cpp to 'scanner'


You're not logged in! Click here to login


Compile Errors


							
Time Limit: 3 Seconds
Memory Limit: 512MB
No. of ACs: 23
Your best score: 0
Source: Dunjudge Archive

Subtask Score
1 15
2 30
3 55
4 0