Problem
Eric works as a security guard at the university, so after a day's work he walks around the building and turns off the lights at night.
The building has n floors and two staircases on the left and right. There are m rooms on each floor along the corridor that connects the left and right stairs. In other words, the building can be represented as a rectangle with n rows and m + 2 columns, where the first and last column — stairs, and m columns in the middle — rooms.
Eric is now standing on the first floor on the left stairs. He wants to turn off the lights everywhere, while he does not want to go up to the floor above before turning off all the lights on the current floor. Of course, Eric must be in the room to turn off the lights. Eric spends one minute walking up the stairs one floor or going to the next room/stairs from the next room or stairs on the same floor. Turning off the lights in the room Eric is in does not take his time.
Help Eric find the minimum time to turn off all the lights in the building.
Note that Eric does not have to return to his original position, and also that he is not required to visit rooms where the lights are already off.
Input:
The first line contains two integers n and m (1 ≤ n ≤ 15, 1 ≤ m ≤ 100) — the number of floors and the number of rooms on each floor, respectively.
The next n lines contain a description of the building. Each line contains a string of zeros and ones of length m + 2 describing one floor (left stairs, then m rooms, then right stairs), where 0 means the lights are off and 1 means the lights are on. The floors are given in order from top to bottom, in particular, the last line describes the first floor.
The first and last characters of each line describe stairs, so they are always 0.
Output:
Print one number — the minimum possible time required to turn off all the lights.
Examples:
| Input |
Output |
2 2
0010
0100 |
5 |
3 4
001000
000010
000010 |
12 |
Explanations:
In the first example, Eric will first go to room 1 on the first floor, and then — to room 2 on the second floor using any ladder.
In the second example, he will go first to the fourth room on the first floor, go up one floor on the right stairs, enter the fourth room on the second floor, go up the right stairs again, go to the second room on the last floor.