#include <bits/stdc++.h>
using namespace std;
int N, S;
pair<int, int> bearStart;
string graph[800];
int bee[800][800];
int bear[800][800];
bool check(int x)
{
memset(bear, -1, sizeof(bear));
deque<pair<int, int>> dq;
dq.push_back(bearStart);
bear[bearStart.first][bearStart.second] = x * S;
while (!dq.empty())
{
pair<int, int> v = dq.front();
dq.pop_front();
if (v.first >= 1 && bear[v.first - 1][v.second] == -1 && graph[v.first - 1][v.second] != 'T' && bear[v.first][v.second] + 1 < bee[v.first - 1][v.second])
{
if (graph[v.first - 1][v.second] == 'D')
return true;
bear[v.first - 1][v.second] = bear[v.first][v.second] + 1;
dq.push_back({v.first - 1, v.second});
}
if (v.second >= 1 && bear[v.first][v.second - 1] == -1 && graph[v.first][v.second - 1] != 'T' && bear[v.first][v.second] + 1 < bee[v.first][v.second - 1])
{
if (graph[v.first][v.second - 1] == 'D')
return true;
bear[v.first][v.second - 1] = bear[v.first][v.second] + 1;
dq.push_back({v.first, v.second - 1});
}
if (v.first < N - 1 && bear[v.first + 1][v.second] == -1 && graph[v.first + 1][v.second] != 'T' && bear[v.first][v.second] + 1 < bee[v.first + 1][v.second])
{
if (graph[v.first + 1][v.second] == 'D')
return true;
bear[v.first + 1][v.second] = bear[v.first][v.second] + 1;
dq.push_back({v.first + 1, v.second});
}
if (v.second < N - 1 && bear[v.first][v.second + 1] == -1 && graph[v.first][v.second + 1] != 'T' && bear[v.first][v.second] + 1 < bee[v.first][v.second + 1])
{
if (graph[v.first][v.second + 1] == 'D')
return true;
bear[v.first][v.second + 1] = bear[v.first][v.second] + 1;
dq.push_back({v.first, v.second + 1});
}
}
return false;
}
int main()
{
cin.sync_with_stdio(0);
cin.tie(0);
memset(bee, -1, sizeof(bee));
cin >> N >> S;
for (int r = 0; r < N; r++)
cin >> graph[r];
deque<pair<int, int>> dq;
for (int r = 0; r < N; r++)
for (int c = 0; c < N; c++)
if (graph[r][c] == 'H')
{
dq.push_back({r, c});
bee[r][c] = 0;
}
else if (graph[r][c] == 'M')
bearStart = {r, c};
else if (graph[r][c] == 'D')
bee[r][c] = 2000000000;
while (!dq.empty())
{
pair<int, int> v = dq.front();
dq.pop_front();
if (v.first >= 1 && bee[v.first - 1][v.second] == -1 && graph[v.first - 1][v.second] != 'T' && graph[v.first - 1][v.second] != 'D')
{
bee[v.first - 1][v.second] = bee[v.first][v.second] + S;
dq.push_back({v.first - 1, v.second});
}
if (v.second >= 1 && bee[v.first][v.second - 1] == -1 && graph[v.first][v.second - 1] != 'T' && graph[v.first][v.second - 1] != 'D')
{
bee[v.first][v.second - 1] = bee[v.first][v.second] + S;
dq.push_back({v.first, v.second - 1});
}
if (v.first < N - 1 && bee[v.first + 1][v.second] == -1 && graph[v.first + 1][v.second] != 'T' && graph[v.first + 1][v.second] != 'D')
{
bee[v.first + 1][v.second] = bee[v.first][v.second] + S;
dq.push_back({v.first + 1, v.second});
}
if (v.second < N - 1 && bee[v.first][v.second + 1] == -1 && graph[v.first][v.second + 1] != 'T' && graph[v.first][v.second + 1] != 'D')
{
bee[v.first][v.second + 1] = bee[v.first][v.second] + S;
dq.push_back({v.first, v.second + 1});
}
}
int lo = 0;
int hi = 20;
lo--;
while (lo < hi)
{
int mid = lo + (hi - lo + 1) / 2;
if (check(mid))
lo = mid;
else
hi = mid - 1;
}
cout << lo;
}
