#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;
using ll = long long;
using ii = pair<int,int>;
using pii = pair<int,ii>;
using aa = array<int,4>;
const int N = 805;
const int INF = 1e9;
const int MOD = 1e9+21;
int n,S,c,u,v,start_x,start_y,home_x,home_y;
int ans = -1,cur = -1;
ii d[N][N];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
char a[N][N];
queue<aa> q;
bool ok(int i,int j){
return min(i,j) >= 1 && max(i,j) <= n && a[i][j] != 'H' && a[i][j] != 'T';
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> n >> S;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
cin >> a[i][j];
if (a[i][j] == 'M'){ //Mecho pos
start_x = i;
start_y = j;
}
if (a[i][j] == 'H'){ //Hives pos
q.push({i,j,0});
}
if (a[i][j] == 'D'){
home_x = i;
home_y = j;
}
}
}
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++) d[i][j] = {0,-1};
}
while (!q.empty()){
c = q.front()[2];
if (c != cur){
queue<ii> qq;
qq.push({start_x,start_y});
d[start_x][start_y] = {0,c};
while (!qq.empty()){
tie(u,v) = qq.front();
qq.pop();
for (int k = 0; k < 4; k++){
int x = u + dx[k];
int y = v + dy[k];
if (ok(x,y) && d[x][y].se == cur){
d[x][y] = {d[u][v].fi + 1,c};
qq.push({x,y});
}
}
}
if (d[home_x][home_y].se == cur){
cout << ans;
return 0;
}
ans = max(ans,c - (d[home_x][home_y].fi + S - 1) / S + 1);
cur = c;
}
u = q.front()[0];
v = q.front()[1];
q.pop();
for (int k = 0; k < 4; k++){
int x = u + dy[k];
int y = v + dy[k];
if (ok(x,y) && a[x][y] != 'D'){
a[x][y] = 'H';
q.push({x,y,c+1});
}
}
}
cout << ans;
return 0;
}
