#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define ll long long
#define FOR(N) for(int i = 0; i < N; ++i)
#define pi pair<int,int>
#define vi vector<int>
#define F first
#define S second
int N, SPS;
string input;
vector<vector<char>> grid; // j+y vertical, i+x horizontal
pi start, endp;
vi dx = {1,0,-1,0};
vi dy = {0,-1,0,1};
vector<vi> bees;
signed main() {
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> N >> SPS;
grid.resize(N, vector<char>(N));
bees.resize(N, vi(N, -1));
queue<pair<int,pi>> bfsbee;
for(int j = 0; j < N; ++j) {
cin >> input;
FOR(N) {
grid[i][j] = input[i];
if (input[i] == 'M') start = {i,j};
if (input[i] == 'D') endp = {i,j};
if (input[i] == 'H') bfsbee.push({0,{i,j}});
//cout << input[i] << endl;
}
}
while(bfsbee.size()) {
int t = bfsbee.front().F;
int x = bfsbee.front().S.F;
int y = bfsbee.front().S.S;
//cout << x << ' ' << y << ' ' << t << endl;
bfsbee.pop();
if (bees[x][y] != -1) continue;
bees[x][y] = t;
FOR(4) {
int bruh1 = x + dx[i];
int bruh2 = y + dy[i];
if (bruh1 >= N || bruh2 >= N || bruh1 < 0 || bruh2 < 0) continue;
if (grid[bruh1][bruh2] == 'T' || grid[bruh1][bruh2] == 'D' || bees[bruh1][bruh2] != -1) continue;
bfsbee.push({t+1, {bruh1, bruh2}});
}
}
int l = -1; int r = 1000000;
while (l != r - 1) {
int m = (l + r) / 2;
bool can = false;
queue<pair<int,pi>> bfs; // SPS, pos
bfs.push({0, start});
vector<vector<bool>> vis(N, vector<bool>(N));
while(bfs.size()) {
int steps = bfs.front().F;
int x = bfs.front().S.F;
int y = bfs.front().S.S;
bfs.pop();
if (vis[x][y]) continue;
vis[x][y] = true;
if (endp == make_pair(x, y)) {can = true; break;}
if (m + steps / SPS >= bees[x][y]) continue;
FOR(4) {
int bruh1 = x + dx[i];
int bruh2 = y + dy[i];
if (bruh1 >= N || bruh2 >= N || bruh1 < 0 || bruh2 < 0) continue;
if (grid[bruh1][bruh2] == 'T' || grid[bruh1][bruh2] == 'H') continue;
bfs.push({steps+1, {bruh1, bruh2}});
}
}
//cout << m << ' ' << l << ' ' << r << ' ' << can << endl;
if (can) l = m ;
else r = m;
}
cout << l << endl;
return 0;
}
