#include<bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define piipi pair<pii, int>
int N = 1e6;
int main()
{
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
int n, s;
cin >> n >> s;
vector<string> grid(n+2);
string ns = "";
for (int i = 0; i < n+2; i++) ns += "T";
grid[0] = ns;
grid[n+1] = ns;
for (int i = 1; i <= n; i++)
{
cin >> grid[i];
grid[i] = "T" + grid[i] + "T";
}
vector<vector<int>> graph(N);
queue<pii> q;
int home = -1;
int mecho = -1;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
int ind = i*(n+2) +j;
if (grid[i][j]=='H') q.push({0, ind});
if (grid[i][j]=='D') home = ind;
if (grid[i][j]=='M') mecho = ind;
if (grid[i][j-1]!='T') graph[ind].push_back(ind-1);
if (grid[i][j+1]!='T') graph[ind].push_back(ind+1);
if (grid[i+1][j]!='T') graph[ind].push_back(ind+n+2);
if (grid[i-1][j]!='T') graph[ind].push_back(ind-n-2);
}
}
if (home == -1 || mecho == -1)
{
cout << -1;
return 0;
}
vector<int> dist(N, N-1);
while (q.size())
{
int i, d;
tie(d, i) = q.front();
q.pop();
if (dist[i]!=N-1) continue;
dist[i] = d;
for (int ele:graph[i])
{
q.push({d+1, ele});
}
}
priority_queue<pii, vector<pii>, less<pii>> toadd;
vector<int> reach(N, 0);
toadd.push({dist[home], home});
for (int i = N-1; i >= 0; i--)
{
while(toadd.size() && toadd.top().first >= i)
{
q.push({0, toadd.top().second});
toadd.pop();
}
while (q.size())
{
int j, d;
tie(d, j) = q.front();
q.pop();
if (reach[j]==1) continue;
reach[j] = 1;
for (int ele:graph[j])
{
if (dist[ele]>=i && d+1 < s) q.push({d+1, ele});
else toadd.push({dist[ele], ele});
}
}
if (reach[mecho])
{
cout << i-1;
return 0;
}
}
cout << -1;
return 0;
}
