from collections import deque
from math import ceil
N, S = map(int, input().split())
a = [input() for _ in range(N)]
dist = [[-1]*N for x in range(N)]
q = deque()
for x in range(N):
for y in range(N):
if a[x][y] == 'H':
q.append((x, y))
dist[x][y] = 0
elif a[x][y] == 'M':
M = (x, y)
elif a[x][y] == 'D':
D = (x, y)
while q:
x, y = q.popleft()
for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
if 0 <= x+dx < N and 0 <= y+dy < N and a[x+dx][y+dy] in 'GM' and dist[x+dx][y+dy] == -1:
dist[x+dx][y+dy] = dist[x][y]+1
q.append((x+dx, y+dy))
distM = [[float('inf')]*N for x in range(N)]
distdiff = [[float('-inf')]*N for x in range(N)]
distM[M[0]][M[1]], distdiff[M[0]][M[1]] = 0, dist[x][y]
distdiff[D[0]][D[1]] = -1
q = deque([M])
while q:
x, y = q.popleft()
if a[x][y] != 'D':
distdiff[x][y] = min(distdiff[x][y], dist[x][y]-ceil(distM[x][y]/S))
for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
if 0 <= x+dx < N and 0 <= y+dy < N and a[x+dx][y+dy] in 'GD' and distM[x][y]+1 <= distM[x+dx][y+dy]:
if distM[x+dx][y+dy] == float('inf'):
distM[x+dx][y+dy] = distM[x][y]+1
q.append((x+dx, y+dy))
distdiff[x+dx][y+dy] = max(distdiff[x][y], distdiff[x+dx][y+dy])
print(distdiff[D[0]][D[1]])
