#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(0); cin.tie(0)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ll long long
struct P{
ll x, y;
};
void dbg_out() { cerr << endl; }
template <typename H, typename... T>
void dbg_out(H h, T... t) { cerr << ' ' << h; dbg_out(t...); }
#define dbg(...) { cerr << #__VA_ARGS__ << ':'; dbg_out(__VA_ARGS__); }
const int N = 801;
char grid[N][N];
int n, s;
vector<vector<int>> bdist (N, vector<int>(N, N*N+1));
pair<int, int> bear;
pair<int, int> home;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int valid(int x, int y){
return x >= 0 && y >= 0 && x < n && y < n;
}
int f(int t){
vector<vector<int>> dist (n, vector<int>(n, n*n+1));
int x, y;
queue<pair<int, int>> q;
dist[bear.first][bear.second] = 0;
q.push(bear);
while (!q.empty()){
tie(x, y) = q.front(); q.pop();
if ((bdist[x][y]-t)*s <= dist[x][y]) continue;
for (int i=0; i<4; i++){
int a = x + dx[i], b = y + dy[i];
if (!valid(a, b) || grid[a][b] == 'T' || dist[a][b] != n*n+1) continue;
dist[a][b] = dist[x][y] + 1;
q.push({a, b});
}
}
return dist[home.first][home.second] != n*n+1;
}
signed main(){
fastio;
cin >> n >> s;
vector<pair<int, int>> bees;
for (int i=0; i<n; i++){
for (int j=0; j<n; j++){
cin >> grid[i][j];
if (grid[i][j] == 'H') bees.push_back({i, j});
if (grid[i][j] == 'M') bear = {i, j};
if (grid[i][j] == 'D') home = {i, j};
}
}
int x, y;
queue<pair<int, int>> q;
for (auto b: bees){
q.push(b);
bdist[b.first][b.second] = 0;
}
while (!q.empty()){
tie(x, y) = q.front(); q.pop();
for (int i=0; i<4; i++){
int a = x + dx[i], b = y + dy[i];
if (!valid(a, b) || grid[a][b] == 'T' || grid[a][b] == 'D' || bdist[a][b] != N*N+1) continue;
bdist[a][b] = bdist[x][y] + 1;
q.push({a, b});
}
}
int l=0, r=n*n, ans=-1;
while (l <= r){
int m = l + (r-l)/2;
if (f(m)){
ans = m;
l = m+1;
}
else r = m-1;
}
cout << ans << '\n';
}
