#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops,fast-math,unsafe-math-optimizations")
#define int long long
#define f first
#define s second
#define pii pair <int, int>
#define iShowSpeed cin.tie(NULL)->sync_with_stdio(false)
#define emb emplace_back
using namespace std;
const int inf = 1e14;
const int mod = 998244353;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
int32_t main(){
iShowSpeed;
int n, k; cin >> n >> k;
char a[n][n];
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) cin >> a[i][j];
vector <vector <int>> bee(n, vector <int> (n, inf)), bear(n, vector <int> (n, inf));
vector <vector <pii>> prev(n, vector <pii> (n, {-1, -1}));
queue <pii> q;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (a[i][j] == 'H') bee[i][j] = 0, q.emplace(i, j);
}
}
while (!q.empty()) {
auto [x, y] = q.front(); q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= n || bee[nx][ny] <= bee[x][y] + 1) continue;
q.emplace(nx, ny);
bee[nx][ny] = bee[x][y] + 1;
}
}
int ex, ey;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (a[i][j] == 'M') bear[i][j] = 0, q.emplace(i, j);
if (a[i][j] == 'D') ex = i, ey = j;
}
}
while (!q.empty()) {
auto [x, y] = q.front(); q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= n || bear[nx][ny] <= bear[x][y] + 1) continue;
q.emplace(nx, ny);
bear[nx][ny] = bear[x][y] + 1;
prev[nx][ny] = {x, y};
}
}
vector <pii> path;
int curx = ex, cury = ey;
while (curx != -1 && cury != -1) {
path.emb(curx, cury);
int tx = curx, ty = cury;
curx = prev[tx][ty].f;
cury = prev[tx][ty].s;
}
reverse(path.begin(), path.end());
path.pop_back();
// for (auto [x, y] : path) cout << x << " " << y << "\n";
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// cout << bee[i][j] << " ";
}
// cout << "\n";
}
// cout << "--------------------\n";
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
bear[i][j] = (bear[i][j] + k - 1) / k;
// cout << bear[i][j] << " ";
}
// cout << "\n";
}
int ans = inf;
for (auto [x, y] : path) {
ans = min(ans, bee[x][y] - bear[x][y]);
}
cout << (ans < 0 ? -1 : ans);
}
