#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, s; cin >> n >> s;
vector<string> g(n);
for(int i = 0; i < n; i++){
cin >> g[i];
}
queue<pair<int, pair<int, int>>> q;
pair<int, int> it;
pair<int, int> it1;
for(int i = 0; i < n; i++){
for(int y = 0; y < n; y++){
if(g[i][y] == 'H'){
q.push({i, {y, -1}});
}else if(g[i][y] == 'M'){
it = {i, y};
}else if(g[i][y] == 'D'){
it1 = {i, y};
}
}
}
vector<vector<int>> d(n, vector<int>(n, 1e9));
while(q.size() > 0){
int x = q.front().first;
int y = q.front().second.first;
int time = q.front().second.second;
q.pop();
if(x < 0 || y < 0 || x >= n || y >= n){
continue;
}
if(d[x][y] != 1e9) continue;
if(g[x][y] == 'T' || g[x][y] == 'D'){
continue;
}
d[x][y] = time+1;
q.push({x-1, {y, d[x][y]}});
q.push({x+1, {y, d[x][y]}});
q.push({x, {y+1, d[x][y]}});
q.push({x, {y-1, d[x][y]}});
}
int low = 0;
int top = n*n;
int ns = -1;
while(low <= top){
int mid = (low + top)/2;
vector<vector<int>> d1(n, vector<int>(n, 1e9));
queue<pair<int, pair<int, int>>> q;
q.push({it.first, {it.second, -1}});
while(q.size() > 0){
int x = q.front().first;
int y = q.front().second.first;
int time = q.front().second.second;
q.pop();
if(x < 0 || y < 0 || x >= n || y >= n){
continue;
}
if(d1[x][y] != 1e9) continue;
if(g[x][y] == 'T'){
continue;
}
if(d[x][y] < mid + (time+1)/s + 1 && d[x][y] != 1e9){
continue;
}
d1[x][y] = time+1;
q.push({x-1, {y, d1[x][y]}});
q.push({x+1, {y, d1[x][y]}});
q.push({x, {y+1, d1[x][y]}});
q.push({x, {y-1, d1[x][y]}});
}
if(d1[it1.first][it1.second] != 1e9){
low = mid+1;
ns = mid;
}else{
top = mid-1;
}
}
cout << ns << "\n";
return 0;
}
