// Jai Shree Ram
#include<bits/stdc++.h>
using namespace std;
/* Abhi-Atg */
#define array int n;cin >> n;vector<long long> v(n);f(i,0,n)cin >> v[i];
#define out(_) for (auto &it :_){cout << it << " " ;}cout<<endl;
#define f(i,l,r) for(int i=l;i<r;i++)
#define ff(i,r,l) for(int i=r;i>=l;i--)
#define pb push_back
#define mod 1000000007
#define INDIA 998244353
#define ll long long
#define all(v) v.begin(),v.end()
#define dbg cout << "Bharat\n"
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define minus cout << "-1\n"
void solve(){
int n,s;cin >> n >> s;
vector<string> v(n);
int mx,my;
int dx,dy;
vector<pair<int,int>> q;
vector<vector<int>> dp(n,vector<int>(n, INDIA));
f(i,0,n){
cin >> v[i];
for(int j=0;j<n;j++){
if(v[i][j]=='M'){
mx=i;my=j;
}else if(v[i][j]=='D'){
dx=i;dy=j;
}else if(v[i][j]=='H'){
q.pb({i,j});
dp[i][j]=0;
}
}
}
int xx[]={0,0,1,-1};
int yy[]={1,-1,0,0};
for(int i=0;i<q.size();i++){
for(int j=0;j<4;j++){
int nx=q[i].first+xx[j];
int ny=q[i].second+yy[j];
if(nx>=0 && ny>=0 && nx<n && ny<n && v[nx][ny]!='T' && v[nx][ny]!='D' && dp[nx][ny]>dp[q[i].first][q[i].second]+1){
dp[nx][ny]=dp[q[i].first][q[i].second]+1;
q.pb({nx,ny});
}
}
}
int mn=-1;
int l=0,r=INDIA;
while(l<=r){
int mid=(l+r)/2;
bool flag=false;
int val=mid;
if(dp[mx][my]>val){
vector<pair<int,int>> q;
q.push_back({mx,my});
vector<vector<bool>> vis(n,vector<bool>(n,false));
vis[mx][my]=true;
while(q.size()){
val++;
for(int st=0;st<s;st++){
vector<pair<int,int>> qq;
for(int i=0;i<q.size();i++){
for(int j=0;j<4;j++){
int nx=q[i].first+xx[j];
int ny=q[i].second+yy[j];
if(nx>=0 && ny>=0 && nx<n && ny<n && v[nx][ny]!='T' && vis[nx][ny]==false){
int cond=0;
if(st==s-1){
cond=(dp[nx][ny]>val);
}else{
cond=(dp[nx][ny]>=val);
}
if(cond){
vis[nx][ny]=true;
qq.pb({nx,ny});
if(nx==dx && ny==dy){
flag=true;
break;
}
}
}
}
if(flag)break;
}
q=qq;
}
}
}
if(flag){
mn=mid;
l=mid+1;
}else r=mid-1;
}
cout << mn << "\n";
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(nullptr);
// #ifndef ONLINE_JUDGE
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// #endif
// freopen("input.in", "r", stdin);
// freopen("output.out", "w", stdout);
int t=1;
// cin >> t;
for(int _=1;_<=t;_++){
// cout<<"Case #"<<_<<": ";
solve();
}
return 0;
}
