Bajtazar's Platform Game

Bajtazar is playing a game on his new computer. In this game there are \(n\) horizontal platforms numbered from \(1\) to \(n\) from top to bottom. Each platform has a length of \(X\), so a position is represented as \((i, x)\) where \(i\) is the platform number and \(x\) is the horizontal position (with \(1\) being the leftmost and \(X\) the rightmost).

The player starts at the left end (i.e. \(x=1\)) of any platform which is safe (i.e. does not contain a hole) and the goal is to reach the right end (i.e. \(x=X\)) of any platform. The player can only move to the right. However, there are holes at some positions on the platforms. It is guaranteed that no two holes are adjacent either horizontally or vertically.

When the player is at \((i, x)\), he can perform one of the following operations:

• F operation: If the cell \((i, x+1)\) does not contain a hole, the player moves to \((i, x+1)\). Otherwise, the player moves to \((i+1, x+1)\) (i.e. drops to the platform below). Note that if \(i = n\) (i.e. the bottom platform) and \((i, x+1)\) is a hole, then this move is not allowed.
• A operation: If \((i, x+1)\) is a hole and \(x+1 < X\), then the player can jump over the hole to \((i, x+2)\). This counts as one jump.
• B operation: If \(i > 1\) and the cell directly above at \((i-1, x)\) is a hole, then the player can jump upward to \((i-1, x+1)\). This also counts as one jump.

Bajtazar wants to know the minimum number of jump operations (i.e. the number of A and B operations) required to complete the game.

Notes on the game board:

• The game board is described by \(n\) rows and each row is a string of length \(X\). A character '0' indicates a safe cell and '1' indicates a hole.
• You may assume that the input guarantees that no two holes are adjacent horizontally or vertically.

inputFormat

The input consists of:

1. A line with two integers \(n\) and \(X\) (the number of platforms and the length of each platform).
2. Then \(n\) lines follow, each containing a string of length \(X\) composed of '0' or '1'. The \(i\)-th line (1-indexed) represents the \(i\)-th platform from the top. '0' means the cell is safe and '1' means there is a hole.

outputFormat

Output a single integer: the minimum number of jump operations (A and B) needed to reach any platform's rightmost cell (i.e. a cell with \(x = X\)). If it is impossible to finish the game, output -1.

sample

3 5
00000
00000
00000

0