#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 9000372036854775800;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define print(arr) for (auto i : arr) cout << i << " "; cout << endl;
typedef vector<vector<int>> vvi;
typedef vector<pair<int, int>> vpi;
typedef vector<int> vi;
typedef pair<int, int> pii;
void setFile(string name) {
freopen((name + "in.txt").c_str(), "r", stdin);
freopen((name + "out.txt").c_str(), "w", stdout);
}
int MOD = 1e9 + 7;
int n, s;
pii pot, home;
bool f(int sleep, vvi dists) {
int n = dists.size();
rep(i, 0, n) {
rep(j, 0, n) {
if (dists[i][j] == INF) continue;
dists[i][j] -= sleep;
if (dists[i][j] <= 0) dists[i][j] = INF;
}
}
// check if valid path exists
vector<vector<bool>> visited(n, vector<bool>(n, false));
queue<vi> q;
q.push({pot.first, pot.second});
visited[pot.first][pot.second] = true;
while (!q.empty()) {
vi curr = q.front(); q.pop();
if (abs(home.first - curr[0]) + abs(home.second - curr[1]) <= s) return true;
vpi dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
trav(d, dir) {
int x = curr[0] + d.first, y = curr[1] + d.second;
if (x < 0 || x >= n || y < 0 || y >= n) continue;
if (visited[x][y]) continue;
if (dists[x][y] == INF) continue;
visited[x][y] = true;
q.push({x, y});
}
}
return false;
}
int last_true_jump(int lo, int hi, vvi &dists) {
lo--;
for (int dif = hi - lo; dif > 0; dif /= 2) {
while (lo + dif <= hi && f(lo + dif, dists)) { lo += dif; }
}
return lo;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> s;
queue<vi> hives;
vector<vector<char>> grid(n, vector<char>(n));
vvi beedist(n, vi(n, INF));
rep(i, 0, n) {
rep(j, 0, n) {
cin >> grid[i][j];
if (grid[i][j] == 'M') {
pot = {i, j};
} else if (grid[i][j] == 'D') {
home = {i, j};
} else if (grid[i][j] == 'H') {
hives.push({i, j, 0});
beedist[i][j] = 0;
}
}
}
vpi dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
while (!hives.empty()) {
vi curr = hives.front(); hives.pop();
trav(d, dir) {
int x = curr[0] + d.first, y = curr[1] + d.second;
if (x < 0 || x >= n || y < 0 || y >= n) continue;
if (grid[x][y] == 'T' || grid[x][y] == 'D') continue;
if (beedist[x][y] > curr[2] + 1) {
beedist[x][y] = curr[2] + 1;
hives.push({x, y, curr[2] + 1});
}
}
}
vvi mydist(n, vi(n, INF));
queue<vi> q;
q.push({pot.first, pot.second, 0});
mydist[pot.first][pot.second] = 0;
while (!q.empty()) {
vi curr = q.front(); q.pop();
trav(d, dir) {
int x = curr[0] + d.first, y = curr[1] + d.second;
if (x < 0 || x >= n || y < 0 || y >= n) continue;
if (grid[x][y] == 'T') continue;
if (mydist[x][y] > curr[2] + 1) {
mydist[x][y] = curr[2] + 1;
q.push({x, y, curr[2] + 1});
}
}
}
vvi dists(n, vi(n, INF));
rep(i, 0, n) {
rep(j, 0, n) {
if (mydist[i][j] == INF) {
dists[i][j] = INF;
continue;
} if (mydist[i][j] == 0) continue;
if (mydist[i][j] % s == 0) {
mydist[i][j] /= s;
} else {
mydist[i][j] /= s;
mydist[i][j]++;
}
dists[i][j] = beedist[i][j] - mydist[i][j];
}
}
// trav(row, dists) {
// trav(i, row) {
// if (i == INF) cout << "-1 ";
// else cout << i << " ";
// }
// cout << endl;
// }
int ans = last_true_jump(0, n*n, dists);
cout << ans << endl;
}
