#include <bits/stdc++.h>
using namespace std;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
bool check(int m, int S, vector<string> G) {
int N = G.size();
queue<pair<int, int>> bqu;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (G[i][j] == 'H') {
bqu.push(make_pair(i, j));
}
}
}
for (int i = 1; i <= m; i++) {
int sz = bqu.size();
for (int t = 0; t < sz; t++) {
int x = bqu.front().first, y = bqu.front().second;
bqu.pop();
for (int d = 0; d < 4; d++) {
int nx = x + dx[d], ny = y + dy[d];
if (nx >= 0 && nx < N && ny >= 0 && ny < N && G[nx][ny] != 'T' && G[nx][ny] != 'H') {
if (G[nx][ny] == 'M' || G[nx][ny] == 'D') {
return false;
}
G[nx][ny] = 'H';
bqu.push(make_pair(nx, ny));
}
}
}
}
queue<pair<int, int>> mqu;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (G[i][j] == 'M') {
mqu.push(make_pair(i, j));
}
}
}
while (true) {
for (int s = 0; s < S; s++) {
int sz = mqu.size();
for (int t = 0; t < sz; t++) {
int x = mqu.front().first, y = mqu.front().second;
mqu.pop();
if (G[x][y] == 'H') {
continue;
}
for (int d = 0; d < 4; d++) {
int nx = x + dx[d], ny = y + dy[d];
if (nx >= 0 && nx < N && ny >= 0 && ny < N && G[nx][ny] != 'T' && G[nx][ny] != 'H' && G[nx][ny] != 'M') {
if (G[nx][ny] == 'D') {
return true;
}
G[nx][ny] = 'M';
mqu.push(make_pair(nx, ny));
}
}
}
}
int sz = bqu.size();
for (int t = 0; t < sz; t++) {
int x = bqu.front().first, y = bqu.front().second;
bqu.pop();
for (int d = 0; d < 4; d++) {
int nx = x + dx[d], ny = y + dy[d];
if (nx >= 0 && nx < N && ny >= 0 && ny < N && G[nx][ny] != 'T' && G[nx][ny] != 'H') {
if (G[nx][ny] == 'D') {
return false;
}
G[nx][ny] = 'H';
bqu.push(make_pair(nx, ny));
}
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int N, S;
cin >> N >> S;
vector<string> G(N);
for (int i = 0; i < N; i++) {
cin >> G[i];
}
int ll = -1, rr = N * N + 1;
while (ll + 1 < rr) {
int mm = ll + (rr - ll) / 2;
if (check(mm, S, G)) {
ll = mm;
} else {
rr = mm;
}
}
cout << ll << '\n';
}
