from collections import deque
def is_reachable_with_waiting_time(wait_time, n, s, L, dp_bees, start, end):
dp = [[float("inf")] * n for _ in range(n)]
dp[start[0]][start[1]] = 0
q = deque([start])
while q:
x, y = q.popleft()
for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
nx, ny = x + dx, y + dy
if 0 <= nx < n and 0 <= ny < n and L[nx][ny] not in "TH":
new_time = dp[x][y] + 1
if new_time < dp[nx][ny] and (new_time / s) < dp_bees[nx][ny] - wait_time:
dp[nx][ny] = new_time
q.append((nx, ny))
return dp[end[0]][end[1]] != float("inf")
def max_waiting_time(n, s, L):
dp_bees = [[float("inf")] * n for _ in range(n)]
bees, start, end = [], (-1, -1), (-1, -1)
# Identify positions of bees, start, and end
for i in range(n):
for j in range(n):
if L[i][j] == "H":
bees.append((i, j))
dp_bees[i][j] = 0
elif L[i][j] == "M":
start = (i, j)
elif L[i][j] == "D":
end = (i, j)
# BFS to compute minimum time for bees to reach each tile
q = deque(bees)
while q:
x, y = q.popleft()
for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
nx, ny = x + dx, y + dy
if 0 <= nx < n and 0 <= ny < n and dp_bees[nx][ny] > dp_bees[x][y] + 1 and L[nx][ny] != "T":
dp_bees[nx][ny] = dp_bees[x][y] + 1
q.append((nx, ny))
# Binary search for the maximum waiting time
low, high, ans = 0, n * n, -1
while low <= high:
mid = (low + high) // 2
if is_reachable_with_waiting_time(mid, n, s, L, dp_bees, start, end):
ans = mid
low = mid + 1
else:
high = mid - 1
return ans
# Read input
def main():
n, s = map(int, input().split())
L = [input().strip() for _ in range(n)]
print(max_waiting_time(n, s, L))
if __name__ == "__main__":
main()
