#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
int n, k;
bool ok = 0;
int mid;
pair<int,int> sta, en;
vector<string> G;
vector<vector<int>> V;
vector<vector<int>> vis;
queue<pair<pair<int,int>,int>> Q, Q2;
void search2(pair<pair<int,int>,int> now){
if(vis[now.f.f][now.f.s])return;
vis[now.f.f][now.f.s] = 1;
if(now.f.f != n-1){
if(V[now.f.f+1][now.f.s] > (now.s+1)/k+mid){
Q2.push({{now.f.f+1,now.f.s},now.s+1});
}
}
if(now.f.s != n-1){
if(V[now.f.f][now.f.s+1] > (now.s+1)/k+mid){
Q2.push({{now.f.f,now.f.s+1},now.s+1});
}
}
if(now.f.f != 0){
if(V[now.f.f-1][now.f.s] > (now.s+1)/k+mid){
Q2.push({{now.f.f-1,now.f.s},now.s+1});
}
}
if(now.f.s != 0){
if(V[now.f.f][now.f.s-1] > (now.s+1)/k+mid){
Q2.push({{now.f.f,now.f.s-1},now.s+1});
}
}
}
void search(pair<pair<int,int>,int> now){
if(now.f.f < 0 || now.f.s < 0 || now.f.f >= n || now.f.s >= n)return;
if(V[now.f.f][now.f.s] != -1)return;
V[now.f.f][now.f.s] = now.s;
Q.push({{now.f.f-1,now.f.s},now.s+1});
Q.push({{now.f.f+1,now.f.s},now.s+1});
Q.push({{now.f.f,now.f.s-1},now.s+1});
Q.push({{now.f.f,now.f.s+1},now.s+1});
}
int main(){
cin >> n >> k;
G.resize(n);
V.resize(n, vector<int> (n,-1));
for(auto &x : G)cin >> x;
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j){
if(G[i][j] == 'T')V[i][j] = -2;
if(G[i][j] == 'M')sta = {i,j};
if(G[i][j] == 'D'){en = {i,j};V[i][j] = 1000000;}
if(G[i][j] == 'H')Q.push({{i,j},0});
}
}
while(!Q.empty()){
auto x = Q.front();
Q.pop();
search(x);
}
//for(int i = 0; i < n; ++i){
//for(int j = 0; j < n; ++j){
//cout << V[i][j] << " ";
//}
//cout << "\n";
//}
int best = -1;
int hi = V[sta.f][sta.s]-1, lo = 0;
while(lo <= hi){
mid = (hi+lo)/2;
vis.clear();
vis.resize(n, vector<int> (n, 0));
Q2.push({sta,0});
ok = 0;
while(!Q2.empty()){
auto x = Q2.front();
Q2.pop();
if(x.f == en){ok = 1;break;}
search2(x);
}
Q2 = queue<pair<pair<int,int>,int>>();
if(ok){lo = mid+1;best = mid;}
else hi = mid-1;
}
cout << best << "\n";
}
