Shortest Path for Delivery Robot

You are given a grid with (m) rows and (n) columns. Each cell of the grid contains either a '1' or a '0'. A cell with '1' is walkable, while a cell with '0' is blocked. A delivery robot starts at the top-left cell (i.e. cell ((0, 0))) and must reach the bottom-right cell (i.e. cell ((m-1, n-1))). The robot is only allowed to move right or down. The length of a path is defined as the number of cells visited (including the starting and ending cells). Your task is to determine the length of the shortest such path. If there is no valid path, output -1.

Formally, find the minimum (k) such that there exists a sequence of coordinates ((x_i, y_i)) for (i=0, 1, \ldots, k-1) with ((x_0, y_0) = (0, 0)) and ((x_{k-1}, y_{k-1}) = (m-1, n-1)), where for every (0 \le i < k-1), the next cell ((x_{i+1}, y_{i+1})) is either ((x_i, y_i+1)) or ((x_i+1, y_i)). If no such sequence exists, print (-1).

inputFormat

The input is read from standard input (stdin).

The first line contains two space-separated integers (m) and (n) — the number of rows and columns of the grid, respectively.

Each of the following (m) lines contains a string of length (n) consisting only of the characters '1' and '0', representing a row of the grid.

outputFormat

Output a single integer to standard output (stdout) — the length of the shortest path from the top-left corner to the bottom-right corner using only rightward and downward moves. If no valid path exists, output -1.## sample

3 3
111
010
111

5