#include <bits/stdc++.h>
using namespace std;
const int nx=805;
int n, s, mn[nx][nx], dx[4]={1, 0, 0, -1}, dy[4]={0, 1, -1, 0}, dp[nx][nx];
char mp[nx][nx];
pair<int, int> st, tg;
queue<pair<int, int>> q;
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>n>>s;
for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) cin>>mp[i][j], mn[i][j]=1e9;
for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) if (mp[i][j]=='M') st={i, j};
for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) if (mp[i][j]=='H') q.push({i, j}), mn[i][j]=0;
for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) if (mp[i][j]=='D') tg={i, j};
while (!q.empty())
{
auto [x, y]=q.front();
q.pop();
for (int i=0; i<4; i++)
{
int cx=x+dx[i], cy=y+dy[i];
if (cx<1||cx>n||cy<1||cy>n||mp[cx][cy]=='T'||mp[cx][cy]=='D') continue;
if (mn[cx][cy]>mn[x][y]+1) mn[cx][cy]=mn[x][y]+1, q.push({cx, cy});
}
}
int l=0, r=2*n;
while (l<r)
{
int md=(l+r+1)/2;
for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) dp[i][j]=1e9;
if (mn[st.first][st.second]<=md)
{
r=md-1;
continue;
}
dp[st.first][st.second]=0;
q.push({st.first, st.second});
while (!q.empty())
{
auto [x, y]=q.front();
q.pop();
for (int i=0; i<4; i++)
{
int cx=x+dx[i], cy=y+dy[i];
if (cx<1||cx>n||cy<1||cy>n||mp[cx][cy]=='T'||mp[cx][cy]=='H') continue;
if (dp[cx][cy]>dp[x][y]+1&&(md+(dp[x][y]+1)/s)<mn[cx][cy]) dp[cx][cy]=dp[x][y]+1, q.push({cx, cy});
}
}
if (dp[tg.first][tg.second]!=1e9) l=md;
else r=md-1;
}
if (l==0) cout<<-1;
else cout<<l;
}
