Monkey Who Wants to Move Like a Horse

Time limit2sMemory limit256 MB

Summary

Find the minimum number of moves for a monkey to reach the bottom-right cell of a grid using normal steps and at most K knight-like jumps over obstacles.

Level: Medium6 of 10
Topics: BFS, Shortest path, Graph, Matrix
Solved: No attempts yet

Problem

A monkey has escaped from a zoo and is traveling through the world. The monkey wants to move like a horse, so it tries to imitate the horse move used by a chess knight on a grid. In the table below, the cells marked x are the cells a horse can move to in one action. This move can jump over obstacles between the start and destination cells.


	x		x
x				x
		Horse
x				x
	x		x

However, the monkey can use this horse-like move at most K times. Every other move must go one cell up, down, left, or right. Diagonal movement is not allowed.

The monkey starts in the upper-left cell of the grid and must reach the lower-right cell. One adjacent move and one horse-like move each count as one action. Given the grid, find the minimum number of actions needed to reach the destination.

Input

The first line contains the maximum number K of horse-like moves the monkey may use.

The second line contains the grid width W and height H.

Each of the next H lines contains W integers. 0 means an empty cell, and 1 means an obstacle. The monkey cannot move onto a cell with an obstacle. The start and destination cells are always empty.

1 <= W, H <= 200, and 0 <= K <= 30.

Output

Print the minimum number of actions needed to reach the destination. If the destination cannot be reached, print -1.

Examples2

Example 1

Input

Expected output

Example 2
Input
```
2
5 2
0 0 1 1 0
0 0 1 1 0
```
Expected output
```
-1
```