말이 되고 싶은 원숭이

동물원에서 탈출한 원숭이가 세상을 여행하려고 한다. 이 원숭이는 말처럼 움직이고 싶어서, 격자판에서 체스 나이트처럼 이동하는 방법을 따라 하려 한다. 말의 이동은 아래 표에서 x로 표시한 칸으로 한 번에 이동하는 것이다. 말 이동은 중간에 있는 장애물을 뛰어넘을 수 있다.

하지만 원숭이는 말처럼 이동하는 동작을 최대 K번만 사용할 수 있다. 그 밖의 이동은 상하좌우로 인접한 칸으로 한 칸 이동하는 것만 가능하며, 대각선 이동은 할 수 없다.

원숭이는 격자판의 왼쪽 위 칸에서 출발해 오른쪽 아래 칸에 도착해야 한다. 상하좌우 이동 한 번과 말 이동 한 번은 모두 동작 1회로 센다. 격자판 정보가 주어질 때, 도착점까지 가기 위해 필요한 최소 동작 수를 구하라.

첫째 줄에 말처럼 이동할 수 있는 최대 횟수 K가 주어진다.

둘째 줄에 격자판의 가로 길이 W와 세로 길이 H가 주어진다.

다음 H개의 줄에는 각 줄마다 W개의 정수가 주어진다. 0은 빈 칸, 1은 장애물이다. 장애물이 있는 칸으로는 이동할 수 없다. 시작점과 도착점은 항상 빈 칸이다.

1 <= W, H <= 200, 0 <= K <= 30이다.

첫째 줄에 원숭이가 도착점까지 가기 위해 필요한 최소 동작 수를 출력한다. 도착할 수 없으면 -1을 출력한다.