걷는 개미

개미는 참 부지런하다. 때로는 널빤지 아래에 집을 짓기도 한다.

여기 한 개미가 정사각형 널빤지로 깔린 직사각형 영역을 걸으며, 집으로 통하는 유일한 구멍을 찾고 있다.

개미가 한 널빤지에서 다른 널빤지로 이동하는 데는 정확히 1초가 걸린다. 즉, 시각 t에 좌표 (x, y)의 널빤지 위에 있는 개미는 시각 t + 1에 다음 좌표의 다섯 널빤지 중 하나 위에 있다.

(x, y), (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1).

개미는 직사각형 영역 밖으로 나갈 수 없다. 같은 널빤지를 여러 번 방문할 수 있다.

곤충은 굶주리기 쉽다. 개미는 굶지 않고 집으로 돌아가야 한다. 개미의 체력은 단위 "HP"로 나타낸다. 처음에 개미의 체력은 6 HP이다. 매초마다 체력을 1 HP씩 잃는다. 개미가 먹이가 있는 널빤지에 도착하면 그곳에서 먹이를 조금 먹고, 시간을 들이지 않고 체력을 최댓값인 6 HP로 회복한다. 먹이는 충분히 많아서 원하는 만큼 여러 번 먹을 수 있다.

개미의 체력이 0 HP가 되면 개미는 죽어 더 이상 움직이지 않는다. 개미가 널빤지로 이동하는 순간 체력이 0 HP가 되면 그 널빤지에 실제로 도달하지 못한다. 그 위에 먹이가 있어도 먹을 수 없고, 그 돌에 구멍이 있어도 집 입구에서 죽어야 한다.

널빤지에 물웅덩이가 있으면 개미는 그곳으로 이동할 수 없다.

여러분의 임무는 개미가 출발 위치에서 양수의 체력을 유지한 채 구멍에 도달하는 데 걸리는 최소 시간을 계산하는 프로그램을 작성하는 것이다. 불가능하다면 불가능함을 판정한다.

입력은 여러 개의 지도로 이루어지며, 각 지도는 직사각형 영역의 크기와 배치를 나타낸다. 지도는 다음 형식으로 주어진다.

w h
d11 d12 d13 ... d1w
d21 d22 d23 ... d2w
     ...
dh1 dh2 dh3 ... dhw

정수 w와 h는 각각 x방향과 y방향의 널빤지 수이다. w와 h는 8 이하이다. 정수 dyx는 좌표 (x, y)의 널빤지 상태를 다음과 같이 나타낸다.

• 0: 널빤지에 물웅덩이가 있어 개미가 그곳으로 이동할 수 없다.
• 1, 2: 널빤지에 아무것도 없고 개미가 그곳으로 이동할 수 있다. '2'는 개미가 처음 서 있는 곳을 나타낸다.
• 3: 널빤지에 집으로 통하는 구멍이 있다.
• 4: 널빤지에 먹이가 있다.

구멍이 있는 널빤지는 오직 하나뿐이다. 먹이가 있는 널빤지는 다섯 개를 넘지 않는다.

입력의 끝은 두 개의 0이 있는 줄로 나타낸다.

입력 줄의 정수들은 하나 이상의 공백 문자로 구분된다.

입력의 각 지도마다 최소 시간을 나타내는 정수 하나를 한 줄에 출력한다. 개미가 집으로 돌아갈 수 없으면 최소 시간 대신 -1을 출력한다.