#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
const int MOD = 1e9 + 7;
const int INF = INT_MAX;
const ll LINF = LLONG_MAX;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(v) v.begin(), v.end()
#define rep(i, a, b) for(int i = a; i < b; ++i)
void solve() {
int N, S;
cin >> N >> S;
vector<vector<char>> grid(N, vector<char>(N));
vector<vector<int>> dB(N, vector<int>(N, INF));
queue<pii> bees;
pii start, end;
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({i, j});
dB[i][j] = 0;
}
if(grid[i][j] == 'M') {
start = {i, j};
grid[i][j] = 'G'; // Mark as walkable after start
}
if(grid[i][j] == 'D') {
end = {i, j};
}
}
}
// BFS to calculate bees' movement times
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
while(!bees.empty()) {
auto [x, y] = bees.front();
bees.pop();
for(int k = 0; k < 4; ++k) {
int nx = x + dx[k];
int ny = y + dy[k];
if(nx >= 0 && nx < N && ny >= 0 && ny < N && grid[nx][ny] != 'T' && grid[nx][ny] != 'D' && dB[nx][ny] == INF) {
dB[nx][ny] = dB[x][y] + 1;
bees.push({nx, ny});
}
}
}
int ans = -1;
int lo = -1, hi = N * N;
while(lo <= hi) {
int mid = lo + (hi - lo) / 2;
queue<pii> q;
vector<vector<int>> d(N, vector<int>(N, INF));
if(dB[start.fi][start.se] > mid) {
d[start.fi][start.se] = 0;
q.push(start);
}
bool found = false;
while(!q.empty() && !found) {
auto [x, y] = q.front();
q.pop();
for(int k = 0; k < 4; ++k) {
int nx = x + dx[k];
int ny = y + dy[k];
if(nx >= 0 && nx < N && ny >= 0 && ny < N) {
if(grid[nx][ny] == 'D') {
found = true;
break;
}
if(grid[nx][ny] != 'T' && grid[nx][ny] != 'H' && d[nx][ny] == INF) {
int bear_time = d[x][y] + 1;
int steps = (bear_time) / S;
if(dB[nx][ny] > mid + steps) {
d[nx][ny] = bear_time;
q.push({nx, ny});
}
}
}
}
if(found) break;
}
if(found) {
ans = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
cout << ans << endl;
}
int main() {
fast;
int t = 1;
while(t--) {
solve();
}
return 0;
}
