#include <bits/stdc++.h>
using namespace std;
bool M2;
#define endl '\n'
#define fi first
#define se second
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()
#define filter(v) v.resize(unique(all(v)) - v.begin())
#define dbg(x) "(" #x << " = " << x << ")"
template<typename T> bool maximize(T &a, T b) {
if(a < b) {
a = b;
return true;
}else return false;
}
template<typename T> bool minimize(T &a, T b) {
if(a > b) {
a = b;
return true;
}else return false;
}
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
const int N = 8e2 + 3;
const char TREE = 'T', GRASS = 'G', HONEY = 'M', HOME = 'D', HIVE = 'H';
int n, s;
char board[N][N];
pii st, ed;
vector<pii> hive;
void input() {
cin >> n >> s;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
cin >> board[i][j];
if(board[i][j] == HIVE)
hive.emplace_back(i, j);
if(board[i][j] == HONEY)
st = {i, j};
if(board[i][j] == HOME)
ed = {i, j};
}
}
}
const int dx[] = {1, 0, -1, 0},
dy[] = {0, 1, 0, -1};
int bee[N][N], mecho[N][N];
bool check(int wait) {
queue<pii> q;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
mecho[i][j] = 1e9;
}
}
mecho[st.fi][st.se] = wait * s;
q.push(st);
while(!q.empty()) {
int u, v; tie(u, v) = q.front(); q.pop();
for(int i = 0; i < 4; i++) {
int x = dx[i] + u, y = dy[i] + v;
if(1 <= x && x <= n && 1 <= y && y <= n && board[x][y] != TREE) {
int cost = mecho[u][v] + 1;
if(cost / s < bee[x][y]) {
if(minimize(mecho[x][y], cost)) {
q.emplace(x, y);
}
}
}
}
}
return mecho[ed.fi][ed.se] < 1e9;
}
void process() {
queue<pii> q;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
bee[i][j] = 1e9;
}
}
for(pii c : hive) {
int x, y; tie(x, y) = c;
bee[x][y] = 0;
q.emplace(x, y);
}
while(!q.empty()) {
int u, v; tie(u, v) = q.front(); q.pop();
for(int i = 0; i < 4; i++) {
int x = dx[i] + u, y = dy[i] + v;
if(1 <= x && x <= n && 1 <= y && y <= n && board[x][y] != TREE && board[x][y] != HOME) {
if(minimize(bee[x][y], bee[u][v] + 1)) {
q.emplace(x, y);
}
}
}
}
int l = 0, r = bee[st.fi][st.se] - 1, result = -1;
while(l <= r) {
int mid = (l + r) >> 1;
if(check(mid)) result = mid, l = mid + 1;
else r = mid - 1;
}
cout << result << endl;
}
bool M1;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
#define task "Date_A_Live"
if(fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
int testcase = 1; // cin >> testcase;
for(int i = 1; i <= testcase; i++) {
input();
process();
}
cerr << "Time Elapsed: " << fixed << setprecision(3) << (1000. * clock() / CLOCKS_PER_SEC) << " MS" << endl;
cerr << "Global Memory Usage: " << abs(&M2 - &M1) << " MB" << endl;
return 0;
}
