#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);
ll N,S;
cin>>N>>S;
pair<ll,ll> start = {-1,-1};
pair<ll,ll> end = {-1,-1};
char arr[N][N];
for(ll i = 0;i < N;i++){
for(ll j = 0;j < N;j++){
cin>>arr[i][j];
if(arr[i][j] == 'M') start = {i,j};
if(arr[i][j] == 'D') end = {i,j};
}
}
queue<pair<ll,ll> > q;
ll fromhive[N][N];
for(ll i = 0;i < N;i++){
for(ll j = 0;j < N;j++){
fromhive[i][j] = 1e18;
if(arr[i][j] == 'H'){
q.push({i,j});
fromhive[i][j] = 0;
}
}
}
int Hy[] = {0,0,-1,1};
int Wx[] = {-1,1,0,0};
while(!q.empty()){
ll y = q.front().first;
ll x = q.front().second;
q.pop();
for(ll i = 0;i < 4;i++){
ll a = y + Hy[i];
ll b = x + Wx[i];
if(a < 0 || a >= N || b < 0 || b >= N || arr[a][b] == 'T' || arr[a][b] == 'D'){
continue;
}
if(fromhive[a][b] == 1e18){
q.push({a,b});
fromhive[a][b] = fromhive[y][x] + 1;
}
}
}
ll high = 1e6 + 5;
ll low = -1;
while(high - low > 1){
ll mid = (high + low) / 2;
ll dist[N][N];
memset(dist,-1,sizeof(dist));
q.push(start);
dist[start.first][start.second] = 0;
ll time = max(0ll,mid);
ll add = 0;
while(true){
queue<pair<ll,ll> > newq;
while(!q.empty()){
ll y = q.front().first;
ll x = q.front().second;
q.pop();
if(dist[y][x] == S + add){
for(ll ind = 0;ind < 4;ind++){
ll aa = y + Hy[ind];
ll bb = x + Wx[ind];
if(aa < 0 || aa >= N || bb < 0 || bb >= N || arr[aa][bb] == 'T'){
continue;
}
if(dist[aa][bb] == -1 && time < fromhive[aa][bb]){
newq.push({y,x});
break;
}
}
}
for(ll i = 0;i < 4;i++){
ll a = y + Hy[i];
ll b = x + Wx[i];
if(a < 0 || a >= N || b < 0 || b >= N || arr[a][b] == 'T'){
continue;
}
if(dist[a][b] == -1 && dist[y][x] + 1 <= S + add && time < fromhive[a][b]){
dist[a][b] = dist[y][x] + 1;
q.push({a,b});
}
}
}
time++;
add += S;
while(!newq.empty()){
q.push(newq.front());
newq.pop();
}
if(q.empty()){
break;
}
}
if(dist[end.first][end.second] == -1){
high = mid;
}else{
low = mid;
}
}
cout<<low<<'\n';
}
