곰돌이

곰돌이가 숲에서 꿀벌이 숨겨 둔 비밀 꿀단지를 발견했다. 단지에 가득 든 꿀을 먹으려는 순간, 근처에 있던 벌 한 마리가 곰돌이를 발견하고 동료 벌들에게 신호를 보냈다. 곰돌이는 곧 수많은 벌이 벌집에서 출발해 자신을 공격하리라는 것을 직감하고, 벌들을 피해 집으로 돌아가기로 한다. 곰돌이는 꿀단지가 놓인 자리에 되도록 오래 머무르며 꿀을 먹은 뒤, 단지를 떠나 안전하게 집에 도착하고 싶다. 곰돌이가 꿀을 먹으며 머무를 수 있는 가장 긴 시간을 구하라.

숲은 $N \times N$ 크기의 격자판이며, 각 칸은 나무, 풀밭, 벌집, 곰돌이의 집 중 하나이다. 곰돌이는 한 번에 상하좌우로 인접한 칸으로만 이동할 수 있고(대각선 이동은 불가능하다), 나무나 벌집이 있는 칸에는 들어갈 수 없으며 오직 풀밭 칸으로만 이동한다. 곰돌이는 1분에 최대 $S$칸까지 이동할 수 있다.

벌이 처음 신호를 보내는 순간, 곰돌이는 꿀단지가 놓인 풀밭 칸에 있다. 벌집이 있는 칸에는 무수히 많은 벌이 있다고 가정한다(벌집 칸은 여러 개일 수 있다). 이 숲의 시계는 1분 단위로 흐르며, 매 분마다 다음 순서로 사건이 일어난다.

1. 곰돌이가 꿀을 먹고 있는 중이라면, 계속 먹을지 아니면 단지를 떠날지 결정한다. 계속 먹기로 하면 그 1분 동안은 이동할 수 없다. 떠나기로 하면 즉시 출발하여 그 1분 동안 최대 $S$칸을 이동한다. 단지를 떠난 뒤에는 꿀을 다시 먹을 수 없다.
2. 곰돌이가 1분 동안 꿀을 먹거나 이동한 뒤, 그 1분이 끝나는 순간 벌들이 퍼진다. 벌들은 자신이 있는 각 칸에서 상하좌우로 인접한 모든 풀밭 칸으로 동시에 한 칸씩 퍼져 나간다. 한 번 벌이 차지한 칸은 이후에도 계속 벌이 있는 상태로 남으므로, 시간이 지날수록 벌이 있는 칸은 점점 늘어난다.

정리하면, 신호를 보내는 순간에는 벌집 칸에만 벌이 있다. 1분이 끝나면 벌집 칸과 그에 인접한 모든 풀밭 칸을 벌이 차지한다. 2분이 끝나면 거기에 다시 인접한 풀밭 칸까지 차지한다. 충분히 긴 시간이 지나면 벌집에서 도달할 수 있는 모든 풀밭 칸을 벌이 차지하게 된다.

곰돌이와 벌은 숲 밖으로 나갈 수 없고, 벌은 곰돌이의 집 칸으로는 들어갈 수 없다. 곰돌이가 꿀을 먹는 시간은 정수(분)이다. 어떤 순간에 벌이 차지한 칸에 곰돌이가 함께 있게 되면 곰돌이는 붙잡힌다.

숲의 지도가 주어질 때, 곰돌이가 벌에게 붙잡히지 않고 집에 도착할 수 있도록 하면서, 꿀단지 자리에서 꿀을 먹으며 머무를 수 있는 가장 긴 시간을 구하는 프로그램을 작성하라.

표준 입력으로 다음 데이터를 읽는다.

• 첫째 줄에 두 정수 $N$과 $S$가 공백으로 구분되어 주어진다.
• 다음 $N$개의 줄에는 각각 $N$개의 문자가 공백 없이 주어져 지도를 나타낸다. 각 문자의 의미는 다음과 같다.
  • T: 나무가 있는 칸
  • G: 풀밭 칸
  • M: 곰돌이의 처음 위치(꿀단지가 있는 칸)이며, 이 칸도 풀밭이다.
  • D: 곰돌이의 집. 곰돌이는 들어갈 수 있으나 벌은 들어갈 수 없다.
  • H: 벌집이 있는 칸

지도에는 M이 정확히 하나, D가 정확히 하나, H가 하나 이상 있다. 곰돌이의 처음 위치에서 집까지 이어지는 풀밭(G) 경로가 적어도 하나 존재하고, 적어도 하나의 벌집에서 꿀단지(곰돌이의 처음 위치)까지 이어지는 풀밭 경로도 적어도 하나 존재한다. 곰돌이의 처음 위치에 곰돌이의 집이나 벌집이 인접해 있을 수도 있다.

• $1 \le N \le 800$
• $1 \le S \le 1{,}000$

표준 출력으로 정수 하나를 한 줄에 출력한다. 이 값은 곰돌이가 처음 위치에서 안전하게 집에 도착할 수 있도록 하면서 꿀을 계속 먹을 수 있는 가장 긴 시간(분)이다.

곰돌이가 벌에게 붙잡히지 않고 집에 도착하는 것이 불가능하면 $-1$을 출력한다.

첫 번째 예제에서 곰돌이는 1분 동안 꿀을 먹은 뒤, 오른쪽으로 이어지는 일직선 최단 경로를 따라 다음 2분 동안 안전하게 집에 도착할 수 있다. 따라서 꿀을 먹을 수 있는 가장 긴 시간은 1분이고, 출력값은 1이다.