#include<bits/stdc++.h>
using namespace std;
// Mecho from IOI 2009
// 1e9+7 -> Home
// -1 -> Grass (yes)
// 0 -> Tree/Hive (no)
// 0, 1 ... Cannot pass from this minute on
vector<vector<int>> forest;
pair<int,int> start;
int n, s;
void bfs(queue<pair<int,int>>& tv) {
pair<int,int> pos;
int i, j;
while(!tv.empty()) {
pos = tv.front();
i = pos.first;
j = pos.second;
tv.pop();
if((i < n-1) && forest[i+1][j] == -1) {
forest[i+1][j] = forest[i][j] + 1;
tv.push({i+1, j});
}
if((i > 0) && forest[i-1][j] == -1) {
forest[i-1][j] = forest[i][j] + 1;
tv.push({i-1, j});
}
if((j < n-1) && forest[i][j+1] == -1) {
forest[i][j+1] = forest[i][j] + 1;
tv.push({i, j+1});
}
if((j > 0) && forest[i][j-1] == -1) {
forest[i][j-1] = forest[i][j] + 1;
tv.push({i, j-1});
}
}
}
bool check(int t) { // A bfs for Mecho
int i, j, c = 0; // Current steps
bool can_reach = false;
vector<vector<bool>> vis(n, vector<bool>(n, false));
queue<pair<int, pair<int,int>>> tv;
pair<int, pair<int,int>> q;
tv.push({t*s,start});
while(!tv.empty()) {
q = tv.front();
i = q.second.first;
j = q.second.second;
c = q.first;
t = (c+1)/s;
tv.pop();
if(forest[i][j] == 1e9+7) return true;
if((i < n-1) && !vis[i+1][j] && forest[i+1][j] > t) {
vis[i+1][j] = true;
tv.push({c+1, {i+1, j}});
}
if((i > 0) && !vis[i-1][j] && forest[i-1][j] > t) {
vis[i-1][j] = true;
tv.push({c+1, {i-1, j}});
}
if((j < n-1) && !vis[i][j+1] && forest[i][j+1] > t) {
vis[i][j+1] = true;
tv.push({c+1, {i, j+1}});
}
if((j > 0) && !vis[i][j-1] && forest[i][j-1] > t) {
vis[i][j-1] = true;
tv.push({c+1, {i, j-1}});
}
}
return false;
}
int search(int maxi) {
//cout << "here o7\n";
int mini = 0;
int midi;
int ans = -1;
while(mini <= maxi) {
midi = mini+(maxi-mini)/2;
if(check(midi)) {
ans = midi;
mini = midi+1;
}
else maxi = midi-1;
//cout << midi << '\n';
}
return ans;
}
int main(){
cin >> n >> s;
char c;
forest = vector<vector<int>>(n, vector<int>(n, -1));
queue<pair<int,int>> tv;
for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) {
cin >> c;
if(c == 'H') {
forest[i][j] = 0;
tv.push({i, j});
}
else if(c == 'D') forest[i][j] = 1e9+7;
else if(c == 'T') forest[i][j] = 0;
else if(c == 'M') start = {i, j};
}
bfs(tv);
//for(auto v : forest) {for(auto u : v) cout << u << ' '; cout << '\n';}
int ans = search(forest[start.first][start.second]);
cout << ans << '\n';
//for(auto v : forest) {for(auto u : v) cout << u << ' '; cout << '\n';}
return 0;
}
