#include <iostream>
#include <string>
#include <queue>
using namespace std;
void floodfillbees(int i, int j);
bool validmecho(int i, int j);
string grid[800];
int bees[800][800];
int dx[] = {0, -1, 1, 0}, dy[] = {-1, 0, 0, 1};
int n, s;
int main()
{
cin >> n >> s;
pair<int, int> mecho = {0, 0};
int mechodist[800][800], mindiff[800][800]{};
for (int i = 0; i < n; i++)
{
cin >> grid[i];
for (int j = 0; j < n; j++)
{
if (grid[i][j] == 'M')
{
mecho = {i, j};
}
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
bees[i][j] = 1e9;
mechodist[i][j] = -1;
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (grid[i][j] == 'H')
{
floodfillbees(i, j);
}
}
}
queue<pair<int, int>> q;
q.push(mecho);
mechodist[mecho.first][mecho.second] = 0;
mindiff[mecho.first][mecho.second] = bees[mecho.first][mecho.second];
int ans = 0;
while (!q.empty())
{
int curri = q.front().first, currj = q.front().second;
q.pop();
if (grid[curri][currj] == 'D')
{
if (mindiff[curri][currj] > 0)
{
ans = max(ans, mindiff[curri][currj] / s);
}
continue;
}
for (int d = 0; d < 4; d++)
{
int nexti = curri + dx[d], nextj = currj + dy[d];
if (!validmecho(nexti, nextj))
{
continue;
}
if (mechodist[nexti][nextj] == -1)
{
mechodist[nexti][nextj] = mechodist[curri][currj] + 1;
mindiff[nexti][nextj] = min(mindiff[curri][currj], bees[nexti][nextj] - mechodist[nexti][nextj]);
q.push({nexti, nextj});
}
}
}
cout << ans << endl;
return 0;
}
bool ongrid(int i, int j)
{
return (i >= 0 && i < n && j >= 0 && j < n);
}
bool validbees(int i, int j)
{
return (ongrid(i, j) && !(grid[i][j] == 'T') && !(grid[i][j] == 'D') && !(grid[i][j] == 'H'));
}
bool validmecho(int i, int j)
{
return (ongrid(i, j) && !(grid[i][j] == 'T'));
}
void floodfillbees(int i, int j)
{
queue<pair<int, int>> q;
q.push({i, j});
bees[i][j] = 0;
while (!q.empty())
{
int curri = q.front().first, currj = q.front().second;
q.pop();
for (int d = 0; d < 4; d++)
{
int nexti = curri + dx[d], nextj = currj + dy[d];
if (validbees(nexti, nextj) && bees[nexti][nextj] > bees[curri][currj] + s)
{
bees[nexti][nextj] = bees[curri][currj] + s;
q.push({nexti, nextj});
}
}
}
}
