Sonic the hedgehog recently graduated from Stanford University and is off on a new mission: to catch the Evil Golden Bear. Unfortunately, Sonic has rolled into bit of a conundrum. He has to run through a city of civilians in order to catch the Bear. Help the hedgehog hunt him down without running over any civilians!

The city is represented by a 2D grid of size $$$N \times M$$$ and consisting of 1's and 0's:

• 1 if the cell contains a civilian
• 0 if the cell does not contain a civilian

To move across the grid, Sonic has only three options every second:

• Accelerate: increment speed by $$$1$$$
• Decelerate: decrement speed by $$$1$$$
• Change Direction (only if speed is $$$0$$$): set direction to either North, South, East, or West

Note that Sonic must choose to accelerate or decelerate at any given second while moving at a positive speed. In other words, he cannot maintain the same positive speed for any two consecutive seconds.

After this decision, and within the same second, Sonic will move <speed> grid spaces in his current direction. None of the spaces he rolls through can contain a civilian, and he cannot move outside of the city limits.

Note that Sonic cannot reduce his speed below $$$0$$$, and he can only change directions when his speed is equal to 0.

If Sonic starts out at cell $$$(1, 1)$$$ facing South and with speed $$$0$$$, and the Golden Bear sits at cell (N, M), how fast can the hedgehog get to the Bear without hitting any civilians along the way?