G. Gridtopia
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the realm of Gridtopia, adventurers find themselves facing a sprawling $$$N \times M$$$ grid. Starting from the upper left corner, their goal is to traverse to the lower right corner, collecting scattered magical artifacts along the way. However, Gridtopia has a peculiar rule: movement is restricted to only rightward or downward steps. Furthermore, each cell of the grid may contain at most one artifact. Given the adventurers are faced with the challenge of planning the minimum number of trips required to ensure all artifacts are collected and no treasure is left unclaimed in their quest across Gridtopia.

Input

The adventure begins with an input of two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N, M \leq 50$$$), representing the grid's dimensions. Following this, $$$N$$$ lines are provided, each containing $$$M$$$ integers. These integers are either $$$0$$$ or $$$1$$$, where $$$0$$$ signifies an empty cell and $$$1$$$ indicates a cell containing an artifact. The task is to navigate this grid, adhering to the movement restrictions, and determine the optimal path to collect all artifacts.

Output

Reveal in a single integer the minimum number of trips required to collect all artifacts from the grid, ensuring that each trip starts at the grid's upper left corner and concludes at the lower right corner. This number represents the adventurer's efficiency and strategic planning in overcoming the unique challenges of Gridtopia.

Examples
Input
2 2
0 1
1 0
Output
2
Input
3 3
1 0 0
0 1 1
1 1 0
Output
2
Input
5 5
0 0 0 0 1
0 0 0 1 0
0 0 1 0 0
0 1 0 0 0
1 0 0 0 0
Output
5