#include <bits/stdc++.h>
using namespace std;
template <typename T>
using v = vector<T>;
using ll = long long;
using pii = pair<int, int>;
#define rep(i, k, n) for (int i = k; i < n; i++)
v<int> dx = {1, 0, -1, 0};
v<int> dy = {0, 1, 0, -1};
bool bfs(v<v<int>> &grid, pii idx, pii end, int S, int m) {
queue<pii> q;
int n = grid.size();
q.push(idx);
v<v<int>> dis(n, v<int> (n, -1));
dis[idx.first][idx.second] = 0;
while (!q.empty()) {
int ni = q.front().first, nj = q.front().second;
//cout << ni << " " << nj << "\n";
q.pop();
rep(i, 0, 4) {
int x = ni + dx[i];
int y = nj + dy[i];
if (x >= 0 && y >= 0 && x < n && y < n && dis[x][y] == -1 && ((dis[ni][nj]+1)/S) < (grid[x][y] - m)) {
dis[x][y] = dis[ni][nj] + 1;
//if (m == 24) cout << dis[x][y] / S << " " << grid[x][y] - m << "\n";
q.push({x, y});
}
}
}
bool can = false;
rep(i, 0, n) {
int x = end.first+dx[i];
int y = end.second+dy[i];
if (x >= 0 && y >= 0 && x < n && y < n && dis[x][y] != -1 && grid[x][y] != -1e9 && (dis[x][y]/S) < (grid[x][y] - m)) can = true;
}
return can;
}
int main() {
int n, s; cin >> n >> s;
v<string> grid(n);
rep(i, 0, n) {
cin >> grid[i];
}
v<v<int>> dis(n, v<int> (n, -1));
pii idx;
pii end;
rep(i, 0, n) {
rep(j, 0, n) {
if (grid[i][j] == 'M') idx = {i, j};
if (grid[i][j] == 'D') end = {i, j};
}
}
int l = -1, r = n*n;
int ans;
while (l <= r) {
int m = (l+r) / 2;
v<v<int>> aux(n, v<int>(n));
v<v<int>> dis(n, v<int> (n, -2));
queue<pii> q;
rep(i, 0, n) {
rep(j, 0, n) {
if (grid[i][j] == 'T') aux[i][j] = -1e9;
if (grid[i][j] == 'H') {
aux[i][j] = -1e9;
q.push({i, j});
dis[i][j] = -1;
}
if (grid[i][j] == 'G' || grid[i][j] == 'D') aux[i][j] = 1e9;
}
}
while (!q.empty()) {
int ni = q.front().first, nj = q.front().second;
q.pop();
rep(i, 0, 4) {
int x = ni + dx[i];
int y = nj + dy[i];
if (x >= 0 && y >= 0 && x < n && y < n && (grid[x][y] == 'G' || grid[x][y] == 'M') && dis[x][y] == -2 && dis[ni][nj] + 1 <= m) {
dis[x][y] = dis[ni][nj] + 1;
aux[x][y] = dis[x][y];
q.push({x, y});
}
}
}
bool can = bfs(aux, idx, end, s, m);
/*
if (m == 24) {
for (auto x : aux) {
for (auto y : x) {
cout << y << " ";
}
cout << endl;
}
}
*/
//cout << m << " " << can << endl;
if (can) {
ans = m;
l = m+1;
}
else r = m-1;
}
cout << ans << "\n";
}
