Monkey Who Wants to Move Like a Horse

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.

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.

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.

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