보물 찾기 2

건덕이는 지난 보물찾기에서 보물을 찾는 데 성공했다. 이제 건덕이는 배를 타고 세계 곳곳을 누비며 보물을 찾는 보물 탐사대의 일원이 되었다.

건덕이는 주변 섬들의 지형이 담긴 가로 $W$칸, 세로 $H$칸의 지도를 구했다. 지도에는 주변 바다의 지형이 나타나 있다. 바다와 암초로 이루어져 있으며, 배는 암초 위를 지나다닐 수 없다. 지도의 가장 왼쪽 위는 $(1, 1)$, 오른쪽 아래는 $(H, W)$이다.

배는 매번 인접한 8칸 중 한 곳으로 이동할 수 있다. $(r, c)$와 인접한 칸은 $\max(|r-x|, |c-y|) = 1$을 만족하는 $(x, y)$이다. 안전한 항해를 위해 배는 지도 바깥으로 나가지 않는다.

바다에는 지도 기준 왼쪽에서 오른쪽으로 빠르게 흐르는 물살이 있다. 물살을 타고 가면 연료가 들지 않지만, 그 외의 이동에는 한 칸당 1의 연료가 소모된다. 예를 들어 배가 $(r, c)$에 있다면 $(r-1, c+1)$, $(r, c+1)$, $(r+1, c+1)$로는 연료 소모 없이 이동할 수 있고, 그 외의 칸으로 이동하려면 1의 연료가 필요하다.

첫 번째 줄에 보물 지도의 세로 길이 $H$와 가로 길이 $W$가 주어진다. ($3 \le H, W \le 500$)

두 번째 줄부터 $H$개의 줄에 걸쳐 지도가 주어진다. 지도는 .#*K 중 한 문자로만 나타나며, 각각 바다, 암초, 보물, 배를 뜻한다. 배와 보물은 지도에 한 번씩만 주어진다.

물살을 헤쳐 보물을 찾기까지 소모하는 연료의 최솟값을 출력한다. 도달할 수 없는 경우에는 $-1$을 출력한다.