#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=810, dx[]={1, -1, 0, 0}, dy[]={0, 0, 1, -1};
int n, s;
char a[N][N];
int d[N][N], f[N][N];
int xm, ym, xd, yd;
bool check(int t){
queue<pair<int, int>> q;
memset(f, 0x3f, sizeof f);
q.emplace(xm, ym); f[xm][ym]=t*s;
if ((f[xm][ym]+s-1)/s>d[xm][ym]) return 0;
while (q.size()){
int x=q.front().first, y=q.front().second; q.pop();
if (x==xd && y==yd) return 1;
for (int i=0; i<4; ++i){
int u=x+dx[i], v=y+dy[i];
if (u<1 || v<1 || u>n || v>n || f[u][v]<1e18 || (f[x][y]+s+1)/s>d[u][v] || a[u][v]=='T') continue;
f[u][v]=f[x][y]+1;
q.emplace(u, v);
}
}
return 0;
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> s;
queue<pair<int, int>> q;
memset(d, 0x3f, sizeof d);
for (int i=1; i<=n; ++i) for (int j=1; j<=n; ++j){
cin >> a[i][j];
if (a[i][j]=='M') xm=i, ym=j;
if (a[i][j]=='D') xd=i, yd=j;
if (a[i][j]=='H'){
d[i][j]=0;
q.emplace(i, j);
}
}
while (q.size()){
int x=q.front().first, y=q.front().second; q.pop();
for (int i=0; i<4; ++i){
int u=x+dx[i], v=y+dy[i];
if (u<1 || v<1 || u>n || v>n || d[u][v]<1e18 || a[u][v]=='T' || a[u][v]=='D') continue;
d[u][v]=d[x][y]+1;
q.emplace(u, v);
}
}
check(2);
int l=0, r=1e9;
while (l<=r){
int mid=(l+r)>>1;
if (check(mid)) l=mid+1;
else r=mid-1;
}
cout << r << '\n';
return 0;
}
