#include <bits/stdc++.h>
using namespace std;
const int Z = 1<<20;
const int dx[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int N, S, h[Z], m[Z], ans = -1, e, r;
string g, _;
void BFS(char src, int *d) {
fill(d, d + N * N, Z);
queue<int> q;
for(int i = N * N; --i >= 0; ) {
if(g[i] == src && ans < h[i])
d[i] = 0, q.push(i);
if(g[i] == 'D') e = i, g[i] = 30;
}
while(!empty(q)) {
int k = q.front(), i = k / N, j = k % N; q.pop();
for(auto &[s, t] : dx) {
int x = i + s, y = j + t, z = x * N + y;
if(min(x, y) < 0 || max(x, y) >= N || d[z] != Z) continue;
if((g[z] & 1 || g[z] == r) && (!r || (d[k] + 1) / S + ans < h[z]))
d[z] = d[k] + 1, q.push(z);
}
}
}
#define gc getchar_unlocked()
void ri(int &I){
char J = I = 0;
for(; J < 48; J=gc);
for(; J > 47; J=gc) I = I * 10 + J - 48;
}
signed main(){
ri(N), ri(S);
for(int i = 0; i < N; i++, gc)
for(int j = 0; j < N; j++)
g += gc;
BFS('H', h);
for(int b = r = 30; --b >= 0; ) {
ans += 1 << b;
BFS('M', m);
if(m[e] == Z) ans -= 1 << b;
}
cout << ans;
}
