#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using pi = pair<int,int>;
#define endl "\n"
#define mp make_pair
void setIO(string name = "") {
ios_base::sync_with_stdio(0); cin.tie(0);
if(sz(name)){
freopen((name+".in").c_str(), "r", stdin);
freopen((name+".out").c_str(), "w", stdout);
}
}
const int inf = 1e9;
const int maxn = 808;
int n, s;
char grid[maxn][maxn];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
vector<vi> dist(maxn, vi(maxn, inf));
vector<vi> beardist(maxn, vi(maxn, -1));
int sx, sy, ex, ey;
bool reachable(int mid){
if (dist[sx][sy]<=mid){
return false;
}
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
beardist[i][j] = -1;
}
}
priority_queue<pair<int, pi>, vector<pair<int, pi>>, greater<pair<int, pi>>> pq;
beardist[sx][sy] = 0;
pq.push({0, {sx, sy}});
while (!pq.empty()){
auto [d, p] = pq.top();
pq.pop();
auto [x, y] = p;
for (int i = 0; i < 4; i++){
int nx = x+dx[i];
int ny = y+dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
if (grid[nx][ny] == 'T' || grid[nx][ny] == 'H') continue;
if (beardist[nx][ny] != -1) continue;
if ((d+1)/s >= dist[nx][ny]-mid) continue;
beardist[nx][ny] = d+1;
pq.push({d+1, {nx, ny}});
}
}
for (int i = 0; i < 4; i++){
int nx = ex+dx[i];
int ny = ey+dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
if (beardist[nx][ny] != -1 && beardist[nx][ny]/s < dist[nx][ny]-mid) return true;
}
return false;
}
int main(){
setIO();
cin>>n>>s;
priority_queue<pair<int, pi>, vector<pair<int, pi>>, greater<pair<int, pi>>> pq;
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
cin>>grid[i][j];
if (grid[i][j] == 'H'){
pq.push({0, {i, j}});
dist[i][j] = 0;
}
if (grid[i][j] == 'M'){
sx = i;
sy = j;
}
if (grid[i][j] == 'D'){
ex = i;
ey = j;
}
}
}
while (!pq.empty()){
auto [d, p] = pq.top();
pq.pop();
auto [x, y] = p;
if (dist[x][y] < d) continue;
for (int i = 0; i < 4; i++){
int nx = x+dx[i];
int ny = y+dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
if (grid[nx][ny] == 'T' || grid[nx][ny] == 'D') continue;
if (dist[nx][ny] > d+1){
dist[nx][ny] = d+1;
pq.push({d+1, {nx, ny}});
}
}
}
int ans = -1;
int l = 0, r = n*n;
while (l <= r){
int mid = (l+r)/2;
if (reachable(mid)){
ans = mid;
l = mid+1;
}
else{
r=mid-1;
}
}
cout<<ans<<endl;
}
