#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define SZ(x) ((int)(x).size())
#define all(x) x.begin(), x.end()
#define debug(x) cout << #x << ": " << x << " "
#define nl cout << "\n"
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int dx[] = {-1, +1, 0, 0};
int dy[] = {0, 0, -1, +1};
const int MAXN = 1e3+100;
int N, S, sx, sy, ex, ey, d[MAXN][MAXN], D[MAXN][MAXN];
char mat[MAXN][MAXN];
bool valid(int x, int y){
return (x >= 0 && x < N && y >= 0 && y < N && mat[x][y] != 'T');
}
bool check(int mid){
if(mid >= d[sx][sy]){
return false;
}
rep(i, 0, N){
rep(j, 0, N){
D[i][j] = INT_MAX;
}
}
D[sx][sy] = 0;
queue<pii> q;
q.push({sx, sy});
while(!q.empty()){
auto [x, y] = q.front();
q.pop();
int dist = (D[x][y] + 1) / S;
rep(i, 0, 4){
int x2 = x + dx[i], y2 = y + dy[i];
if(valid(x2, y2) && D[x2][y2] == INT_MAX && d[x2][y2] > dist + mid){
D[x2][y2] = D[x][y] + 1;
q.push({x2, y2});
}
}
}
if(D[ex][ey] != INT_MAX)
return true;
return false;
}
void solve(){
cin >> N >> S;
queue<pii> q;
rep(i, 0, N){
string s; cin >> s;
rep(j, 0, N){
char c = mat[i][j] = s[j];
d[i][j] = INT_MAX;
if(c == 'H'){
d[i][j] = 0;
q.push({i, j});
}
if(c == 'M'){
sx = i, sy = j;
}
if(c == 'D'){
ex = i, ey = j;
}
}
}
while(!q.empty()){
auto [x, y] = q.front();
q.pop();
rep(i, 0, 4){
int x2 = x + dx[i], y2 = y + dy[i];
if(valid(x2, y2) && d[x2][y2] == INT_MAX && mat[x2][y2] != 'D'){
d[x2][y2] = d[x][y] + 1;
q.push({x2, y2});
}
}
}
int l = -1, r = 1e9;
while(r - l > 1){
int m = (l + r) / 2;
if(check(m)) l = m;
else r = m;
}
cout << l;
}
int main(){
ios_base::sync_with_stdio(false), cin.tie(nullptr);
solve();
return 0;
}
