from collections import *
n,s = map(int, input().split())
grid = [list(input()) for i in range(n)]
hives = []
start = []
end = []
for i in range(n):
for j in range(n):
if grid[i][j] == "M":
start = [i,j]
elif grid[i][j] == "D":
end = [i,j]
elif grid[i][j] == "H":
hives.append([i,j])
grid[i][j] = 0
def bfsinit():
d = deque()
for i in hives:
d.append(i+[0])
while len(d):
node = d.popleft()
for a,b in [(0,1), (0,-1), (1, 0), (-1, 0)]:
a += node[0]
b += node[1]
if 0<=a<n and 0<=b<n:
if grid[a][b] == "G" or grid[a][b] == "M":
d.append([a,b,node[2]+1])
grid[a][b] = node[2]+1
visited = [[False for i in range(n)] for i in range(n)]
def test(time):
d = deque()
for i in range(n):
for j in range(n):
visited[i][j] = False
d.append(start+[0])
while len(d):
node = d.popleft()
if node[0] == end[0] and node[1]==end[1]:
return True
for a,b in [(0,1), (0,-1), (1, 0), (-1, 0)]:
a += node[0]
b += node[1]
if 0<=a<n and 0<=b<n and not visited[a][b]:
if grid[a][b]=="T":
continue
if grid[a][b] == "D" or int(grid[a][b]) > time+(node[2]+1)//s:
d.append([a,b,node[2]+1])
visited[a][b] = True
return False
bfsinit()
lo = -1
hi = n*n
while lo<hi:
mid = lo+(hi-lo+1)//2
if test(mid):
lo = mid
else:
hi = mid-1
print(lo)
