#include<bits/stdc++.h>
using namespace std;
#define FOR(i, x, y) for(int i = x; i < y; ++i)
#define pb push_back
#define x first
#define y second
int n;
int S;
struct spair{
int x;
int y;
};
bool inside(int a, int b){
if ((a >= 0 && b >= 0) && (a < n && b < n)){
return true;
}
return false;
}
struct node{
char c;
int d = -1;
bool vis = false;
spair sp = {-1, 0};
};
vector<vector<node>> g;
vector<pair<int, int>> D;
void bfs(vector<pair<int, int>> start){
queue<pair<pair<int, int>, int>> q;
FOR(i, 0, start.size()){
q.push({start[i], 0});
}
while (!q.empty()){
pair<pair<int, int>, int> tmp = q.front();
q.pop();
if (!g[tmp.x.x][tmp.x.y].vis){
g[tmp.x.x][tmp.x.y].vis = true;
g[tmp.x.x][tmp.x.y].d = tmp.y;
FOR(i, 0, 4){
int nx = tmp.x.x + D[i].x;
int ny = tmp.x.y + D[i].y;
if ((inside(nx, ny) &&!g[nx][ny].vis) &&
(g[nx][ny].c != 'T' && g[nx][ny].c != 'D')){
q.push({{nx, ny}, tmp.y + 1});
}
}
}
}
}
bool operator < (spair a, spair b){
if (a.x == b.x){
return a.y > b.y;
}
return a.x < b.x;
}
void fin_bfs(pair<int, int> end){
priority_queue<pair<spair, pair<int, int>>> q;
q.push({{INT_MAX - 1, 0}, end});
while(!q.empty()){
auto tmp = q.top();
q.pop();
// cout << tmp.x.x << " " << tmp.x.y << "\n";
if (g[tmp.y.x][tmp.y.y].sp < tmp.x){
// cout << "curent node: " << tmp.y.x << " " << tmp.y.y << "\n";
g[tmp.y.x][tmp.y.y].sp = tmp.x;
FOR(i, 0, 4){
int nx = tmp.y.x + D[i].x;
int ny = tmp.y.y + D[i].y;
if (inside(nx, ny)&& g[nx][ny].c != 'T'){
spair cur;
cur.x = tmp.x.x;
cur.y = tmp.x.y;
cur.y++;
if (cur.y > S){
cur.y = 1;
cur.x--;
}
if (cur.x > g[nx][ny].d){
cur.x = g[nx][ny].d;
cur.y = 1;
}
if (g[nx][ny].sp < cur){
q.push({cur, {nx, ny}});
}
}
}
}
}
}
int main(){
D = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
cin >> n >> S;
g.resize(n, vector<node>(n));
vector<pair<int, int>> start;
pair<int, int> end;
pair<int, int> s;
FOR(i, 0, n){
FOR(j, 0, n){
cin >> g[i][j].c;
if(g[i][j].c == 'H'){
start.pb({i, j});
}
if (g[i][j].c == 'D'){
end.x = i;
end.y = j;
}
if (g[i][j].c == 'M'){
s = {i, j};
}
}
}
bfs(start);
/* FOR(i, 0, g.size()){
FOR(j, 0, g[i].size()){
cout << g[i][j].d << " ";
}
cout << "\n";
}*/
fin_bfs(end);
/*FOR(i, 0, g.size()){
FOR(j, 0, g[i].size()){
cout << "(" << g[i][j].sp.x << ", " << g[i][j].sp.y << ") ";
}
cout << "\n";
}*/
if (g[s.x][s.y].sp.x == -1){
cout << "-1\n";
}
else{
cout << g[s.x][s.y].sp.x - 1 << "\n";
}
}
