#include <bits/stdc++.h>
using namespace std;
struct Cell
{
int x, y, p;
};
int n;
int s;
char ma[801][801];
int enj[801][801];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
bool isvalid(int i, int j)
{
return i >= 1 && i <= n && j >= 1 && j <= n;
}
bool monotone(int m)
{
queue<Cell> q;
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= n; ++j)
{
if(ma[i][j] == 'M')
{
Cell nodo;
nodo.x = i;
nodo.y = j;
nodo.p = 0;
q.push(nodo);
}
}
}
while(!q.empty())
{
Cell Nodo;
Nodo = q.front();
q.pop();
for(int i = 0; i < 4; ++i)
{
for(int j = 1; j <= s; ++j)
{
int nx = Nodo.x + j * dx[i];
int ny = Nodo.y + j * dy[i];
if(!isvalid(nx, ny) && ma[nx][ny] == 'H' && ma[nx][ny] == 'T') break;
if(m <= enj[nx][ny] && ma[nx][ny] != 'M')
{
if(ma[nx][ny] == 'D')
{
return true;
}
ma[nx][ny] = 'M';
q.push({nx, ny, Nodo.p + 1});
}
}
}
}
return false;
}
int BSOTA(int a, int b)
{
while(a + 1 < b)
{
int m = (a + b) / 2;
if(monotone(m))
{
a = m;
}
else
{
b = m;
}
}
return a;
}
int main()
{
cin.tie(0) -> sync_with_stdio(0);
cin >> n >> s;
pair<int, int> pos;
queue<pair<int, int> > q;
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= n; ++j)
{
cin >> ma[i][j];
if(ma[i][j] == 'H')
{
q.push(make_pair(i, j));
enj[i][j] = 0;
}
else
{
enj[i][j] = INT_MAX;
}
if(ma[i][j] == 'M')
{
pos.first = i;
pos.second = j;
}
}
}
while(!q.empty())
{
int i2 = q.front().first, j2 = q.front().second;
q.pop();
for(int i = 0; i < 4; ++i)
{
int nx = dx[i] + i2;
int ny = dy[i] + j2;
if(isvalid(nx, ny) && ma[nx][ny] != 'D' && ma[nx][ny] != 'T' && ma[nx][ny] != 'H' && enj[nx][ny] == INT_MAX)
{
q.push(make_pair(nx, ny));
enj[nx][ny] = enj[i2][j2] + 1;
}
}
}
int maxx = enj[pos.first][pos.second];
cout << BSOTA(0, maxx - 2);
}
