#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;
using pll = pair<ll, ll>;
ll x, y;
vector<ll> mx = {1, -1, 0, 0}, my = {0, 0, 1, -1};
bool good(ll n, ll s, vector<string>& board, vector<vector<ll>>& disfh, ll m) {
if (disfh[x][y] <= m) return false;
vector<vector<ll>> dis(n, vector<ll> (n, -1));
dis[x][y] = 0;
queue<vector<ll>> q;
q.push({x, y});
while (!q.empty()) {
auto v = q.front();
q.pop();
if (board[v[0]][v[1]] == 'D') {
return true;
}
for (ll i = 0; i < 4; i++) {
ll nx = v[0] + mx[i], ny = v[1] + my[i];
if (nx >= n || nx < 0 || ny >= n || ny < 0) continue;
if (dis[nx][ny] != -1) continue;
if (board[nx][ny] == 'T') continue;
ll bear_time = m + (dis[v[0]][v[1]] + 1) / s;
if (((bear_time)) >= disfh[nx][ny] && board[nx][ny] != 'D') continue;
dis[nx][ny] = dis[v[0]][v[1]] + 1;
q.push({nx, ny});
}
}
return false;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
//___________________________
ll n, s; cin >> n >> s;
vector<string> board(n);
for (ll i = 0; i < n; i++) cin >> board[i];
//___________________________
vector<vector<ll>> disfh(n, vector<ll>(n, -1));
queue<vector<ll>> q;
ll dx = 0, dy = 0;
for (ll i = 0; i < n; i++) {
for (ll j = 0; j < n; j++) {
if (board[i][j] == 'H') q.push({i, j}), disfh[i][j] = 0;
if (board[i][j] == 'M') x = i, y = j;
if (board[i][j] == 'D') dx = i, dy = j;
}
}
disfh[dx][dy] = 1e18;
while (!q.empty()) {
auto v = q.front();
q.pop();
for (ll i = 0; i < 4; i++) {
ll nx = v[0]+mx[i], ny = v[1]+my[i];
if (nx >= n || nx < 0 || ny >= n || ny < 0) continue;
if (disfh[nx][ny] != -1) continue;
if (board[nx][ny] == 'T' || board[nx][ny] == 'D') continue;
disfh[nx][ny] = disfh[v[0]][v[1]]+1;
q.push({nx, ny});
}
}
ll ans = 1e18;
if (!good(n, s, board, disfh, 0)) {
cout << -1 << endl;
return 0;
}
ll l = 0, r = 1e18;
while (l <= r) {
ll m = (l+r)/2;
if (good(n, s, board, disfh, m)) {
l = m+1;
ans = m;
}
else r = m-1;
}
cout << ans << endl;
return 0;
}
