#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
#define int short
#define ld double
#define pii pair<int,int>
#define rand() abs((rand()<<15)|rand())
#define randll() abs(((long long)rand()<<30)|rand())
const int MOD = 1000000007;
char grid[805][805];
int dist1[805][805];
pair<int,int> dist3[805][805];
int dist2[805][805];
int dist[805][805];
int vis[805][805];
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
long long seed;
asm("rdtsc" : "=A"(seed));
srand(seed);
int n, s;
cin >> n >> s;
int si, sj;
int fi, fj;
vector<pair<int,int>> p;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
cin >> grid[i][j];
if(grid[i][j]=='M') {
si = i;
sj = j;
}
if(grid[i][j]=='D') {
fi = i;
fj = j;
}
if(grid[i][j]=='H') {
p.push_back({i,j});
}
if(grid[i][j]=='T') grid[i][j]=0;
}
}
vector<int> di = {1,0,-1,0};
vector<int> dj = {0,1,0,-1};
queue<pair<int,pair<int,int>>> q;
memset(dist1,-1,sizeof(dist1));
dist1[si][sj]=0;
q.push({0,{si,sj}});
while(!q.empty()) {
int d = q.front().first;
int i = q.front().second.first;
int j = q.front().second.second;
q.pop();
for(int x = 0; x < 4; x++) {
if(grid[i+di[x]][j+dj[x]] == 0) continue;
if(dist1[i+di[x]][j+dj[x]] != -1) continue;
dist1[i+di[x]][j+dj[x]] = d+1;
q.push({d+1,{i+di[x],j+dj[x]}});
}
}
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(dist1[i][j]>0) {
dist3[i][j] = {(dist1[i][j]+s-1)/s,(dist1[i][j]+s-1)%s};
}
memset(dist2,-1,sizeof(dist2));
for(auto pp: p) {
int pi = pp.first;
int pj = pp.second;
dist2[pi][pj]=0;
q.push({0,{pi,pj}});
}
while(!q.empty()) {
int d = q.front().first;
int i = q.front().second.first;
int j = q.front().second.second;
q.pop();
for(int x = 0; x < 4; x++) {
if(grid[i+di[x]][j+dj[x]] == 0) continue;
if(dist2[i+di[x]][j+dj[x]] != -1) continue;
if(grid[i+di[x]][j+dj[x]] == 'D') continue;
dist2[i+di[x]][j+dj[x]] = d+1;
q.push({d+1,{i+di[x],j+dj[x]}});
}
}
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(dist1[i][j]>=0) {
dist[i][j] = dist2[i][j]-dist3[i][j].first-(dist3[i][j].second==s-1);
}
// for(int i = 1; i <= n; i++) {
// for(int j = 1; j <= n; j++) {
// cerr << dist3[i][j].first << ":" << dist3[i][j].second << " ";
// }
// cerr << endl;
// }
// cerr << endl;
// for(int i = 1; i <= n; i++) {
// for(int j = 1; j <= n; j++) {
// cerr << dist2[i][j] << " ";
// }
// cerr << endl;
// }
// cerr << endl;
// for(int i = 1; i <= n; i++) {
// for(int j = 1; j <= n; j++) {
// cerr << dist[i][j] << " ";
// }
// cerr << endl;
// }
// cerr << endl;
priority_queue<pair<int,pair<int,int>>> pq;
pq.push({dist[si][sj], {si, sj}});
int ans = dist[si][sj];
bool toBreak = 0;
while(!pq.empty()) {
int d = pq.top().first;
int i = pq.top().second.first;
int j = pq.top().second.second;
pq.pop();
ans = min(ans, d);
if(i==fi && j == fj) break;
for(int x = 0; x < 4; x++) {
if(grid[i+di[x]][j+dj[x]] == 'D') {toBreak = 1; break;}
if(grid[i+di[x]][j+dj[x]] == 0) continue;
if(dist1[i+di[x]][j+dj[x]] <= 0) continue;
if(vis[i+di[x]][j+dj[x]]) continue;
vis[i+di[x]][j+dj[x]] = 1;
pq.push({dist[i+di[x]][j+dj[x]],{i+di[x],j+dj[x]}});
}
if(toBreak)break;
}
cout << ans << endl;
}
