#include <bits/stdc++.h>
using namespace std;
int mat[1000][1000];
int tajm[1000][1000];
int dist[1000][1000];
int si, sj;
int n, s;
const int INF = 1000000007;
bool moze(int dis, int i, int j, int t){
if(i < 1 || i > n || j < 1 || j > n) return 0;
if(mat[i][j] == -1) return 0;
dis++;
if(dis/s+t >= tajm[i][j]) return 0;
if(dis >= dist[i][j]) return 0;
dist[i][j] = dis;
return 1;
}
bool bfs(int t){
queue <pair <int, int>> q;
q.push({si, sj});
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
dist[i][j] = INF;
}
}
dist[si][sj] = 0;
while(!q.empty()){
int i = q.front().first;
int j = q.front().second;
int dis = dist[i][j];
q.pop();
if(mat[i][j] == 2) return 1;
if(moze(dis, i-1, j, t)) q.push({i-1, j});
if(moze(dis, i+1, j, t)) q.push({i+1, j});
if(moze(dis, i, j-1, t)) q.push({i, j-1});
if(moze(dis, i, j+1, t)) q.push({i, j+1});
}
return 0;
}
int main(){
cin >> n >> s;
queue <pair <int, int>> q;
for(int i=1; i<=n; i++){
string str;
cin >> str;
for(int j=0; j<n; j++){
tajm[i][j+1] = INF;
if(str[j] == 'T') mat[i][j+1] = -1;
if(str[j] == 'H'){mat[i][j+1] = -2; q.push({i, j+1}); tajm[i][j+1] = 0;}
if(str[j] == 'M'){mat[i][j+1] = 1; si = i; sj = j+1;}
if(str[j] == 'D') mat[i][j+1] = 2;
}
}
while(!q.empty()){
int i = q.front().first;
int j = q.front().second;
q.pop();
int tren = tajm[i][j];
if(mat[i-1][j] > -1 && mat[i-1][j] < 2 && tajm[i-1][j] > tren+1){tajm[i-1][j] = tren+1; q.push({i-1, j});}
if(mat[i+1][j] > -1 && mat[i+1][j] < 2 && tajm[i+1][j] > tren+1){tajm[i+1][j] = tren+1; q.push({i+1, j});}
if(mat[i][j-1] > -1 && mat[i][j-1] < 2 && tajm[i][j-1] > tren+1){tajm[i][j-1] = tren+1; q.push({i, j-1});}
if(mat[i][j+1] > -1 && mat[i][j+1] < 2 && tajm[i][j+1] > tren+1){tajm[i][j+1] = tren+1; q.push({i, j+1});}
}
int maxres=-1;
int l=0, r = tajm[si][sj]-1;
while(l <= r){
int mid = (l+r)/2;
if(bfs(mid)){maxres = mid; l = mid+1;}
else r = mid-1;
}
cout << maxres;
return 0;
}
