#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
const int mxN=8e2;
char c[mxN][mxN];
int vis[mxN][mxN];
bool vis1[mxN][mxN];
pair<int, int> st, ed;
int n, s;
int dx[4]={0, 0, 1, -1};
int dy[4]={1, -1, 0, 0};
bool valid(int x, int y) {
return (x>=0&&x<n&&y>=0&&y<n&&c[x][y]!='T');
}
bool check(int x) {
queue<array<int, 4>> q;//x y step state_s
q.push({st.ff, st.ss, x+1, 0});
memset(vis1, 0, sizeof(vis1));
vis1[st.ff][st.ss]=1;
while(q.size()) {
auto [xx, yy, step, state]=q.front();
if(ed.ff==xx&&ed.ss==yy) return 1;
q.pop();
for(int i=0; i<4; i++) {
int nx=xx+dx[i], ny=yy+dy[i];
if(valid(nx, ny)&&vis[nx][ny]>step&&!vis1[nx][ny]) {
state++;
vis1[nx][ny]=1;
if(state==s) {
// if(step+1==vis[nx][ny]) continue;
q.push({nx, ny, step+1, 1});
} else {
q.push({nx, ny, step, state+1});
}
}
}
}
return 0;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin>>n>>s;
queue<array<int, 3>> q;
memset(vis, 0x3f, sizeof(vis));
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
cin>>c[i][j];// t g m d h
if(c[i][j]=='M') st={i, j};
if(c[i][j]=='D') ed={i, j};
if(c[i][j]=='H') q.push({i, j, 0}), vis[i][j]=0;
}
}
while(q.size()) {
auto [x, y, now]=q.front();
q.pop();
for(int i=0; i<4; i++) {
int nx=x+dx[i], ny=y+dy[i];
if(vis[nx][ny]==0x3f3f3f3f&&valid(nx, ny)) {
vis[nx][ny]=now+1;
q.push({nx, ny, now+1});
}
}
}
int l=0, r=s, ans=-1;
while(l<=r) {
int mid=(l+r)/2;
if(check(mid)) {
ans=mid;
l=mid+1;
} else {
r=mid-1;
}
}
cout<<ans<<"\n";
return 0;
}
