귀엽기만 한 게 아닌 한별 양

당신은 엄청난 불행 체질을 갖고 태어났다. 다행히 당신에게는 불행 체질을 받아내 주는 여자친구 한별이가 있다. 한별이는 운동신경이 매우 뛰어나 당신에게 닥치는 불상사들을 막아내주곤 한다. 하지만 한별이에게도 한계가 있어서, 연속해서 너무 많은 불상사가 생기면 당신을 온전히 지켜주지 못하게 된다.

현재 당신과 한별이는 학교에서 집으로 귀가하는 중이다. 마을은 $N\times M$ 형태의 격자이며, 당신과 한별이는 상하좌우로 인접한 칸으로만 이동할 수 있다. 일부 칸에는 벽이 있어 들어갈 수 없다. 또, 당신은 한별이에게 길치처럼 보이고 싶지 않기 때문에, 바로 직전에 방문한 칸으로 되돌아가지 않는다.

오늘은 한별이가 당신의 집으로 놀러 가기로 한 날이라, 집에 최대한 빨리 가려고 한다. 당신은 십수 년간의 경험으로 마을의 각 좌표에서 일어나는 불상사의 개수를 미리 알고 있다. 가장 최근에 지나온 3개 이하 칸의 불상사 개수 합이 $K$개를 넘으면, 한별이도 당신을 지켜주지 못해 당신이 부상을 입게 된다. 또, 당신의 불행 체질은 정말 엄청나서, 방문한 칸을 다시 방문할 때마다 같은 개수의 불상사가 다시 일어난다. 당신은 부상을 입지 않고 안전하게 귀가할 수 있을까?

첫 번째 줄에 마을의 세로 크기 $N$, 가로 크기 $M$, 한별이가 연속해서 막을 수 있는 불상사의 개수 $K$가 주어진다. ($2\leq N,M\leq 1\,000$, $0\leq K\leq 27$)

다음 $N$개의 줄에 마을의 상태가 주어진다. 각 줄은 길이 $M$의 문자열이다. S는 학교, H는 집, X는 이동할 수 없는 벽을 의미한다. 그 밖의 칸에는 해당 좌표에서 일어나는 불상사의 개수가 0부터 9까지의 숫자로 주어진다. 학교와 집은 각각 한 개씩만 있으며, 학교와 집에서는 불상사가 일어나지 않는다.

학교에서 집으로 안전하게 이동할 수 있을 때, 가능한 경로 중 최단 거리를 출력한다. 안전하게 귀가할 수 없다면 -1을 출력한다.