#include <bits/stdc++.h>
using namespace std;
#define A first
#define B second
#define MP make_pair
#define ms(a, x) memset(a, x, sizeof(a))
#define boost() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long double, long double> pld;
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);
const int mxN=805;
char grid[mxN][mxN];
int dist[2][mxN][mxN];
queue <pii> q;
vector <pii> moves={{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
int n, s;
bool valid(int i, int j){
if(i >= 1 && i <= n && j >= 1 && j <= n && grid[i][j] != 'H' && grid[i][j] != 'T')
return true;
return false;
}
void dfs(int i, int j, int od, int rest, int d=0){
if(d > s) return;
if(dist[1][i][j] == -1 && od+1 < dist[0][i][j] + (grid[i][j] == 'D')-rest){
dist[1][i][j] = od+1;
q.push({i, j});
}
for(auto [x, y]:moves){
if(dist[1][i+x][j+y] == -1 && valid(i+x, j+y)){
dfs(i+x, j+y, od, rest, d+1);
}
}
}
void bfs(){
while(!q.empty()){
pii u = q.front();
q.pop();
for(auto [x, y]:moves){
if(valid(u.A+x, u.B+y) && dist[0][u.A+x][u.B+y] == -1){
dist[0][u.A+x][u.B+y] = dist[0][u.A][u.B]+1;
q.push({u.A+x, u.B+y});
}
}
}
}
void bfs2(int rest){
while(!q.empty()){
pii u = q.front();
q.pop();
dfs(u.A, u.B, dist[1][u.A][u.B], rest);
}
}
int main(){
ms(dist, -1);
cin >> n >> s;
pii ip, ep;
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
cin >> grid[i][j];
if(grid[i][j] == 'H'){
q.push({i, j});
dist[0][i][j]=0;
}
else if(grid[i][j] == 'M')
ip={i, j};
else if(grid[i][j] == 'D')
ep={i, j};
}
}
int st=1, en=1e9, mid, ans=-1;
bfs();
while(st<=en){
mid = (st+en)/2;
q.push(ip);
ms(dist[1], -1);
dist[1][ip.A][ip.B]=0;
bfs2(mid);
if(dist[1][ep.A][ep.B] != -1){
ans = mid;
st = mid+1;
}
else
en = mid-1;
}
// cout << dist[1][4][4] << " " << dist[0][4][4] << endl;
cout << ans;
}
