#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
#define all(x) x.begin(), x.end()
int n, s, times[802][802];
vector<string> v(802);
pair<int, int> st, en;
const int dx[4] = {0, 0, -1, 1};
const int dy[4] = {-1, 1, 0, 0};
inline bool valid(int x, int y) {
return (x >= 0 && x < n && y >= 0 && y < n && v[x][y] != 'T');
}
bool check(int m) {
if (m >= times[st.first][st.second]) return 0;
queue<pair<int, int>> q;
q.push(st);
int vis[n + 2][n + 2];
memset(vis, -1, sizeof(vis));
vis[st.first][st.second] = m;
while(!q.empty()){
int x = q.front().first, y = q.front().second;
q.pop();
int dist = vis[x][y];
for (int d = 0; d < 4; d++) {
int nx = x + dx[d], ny = y + dy[d];
if (valid(nx, ny) && dist + (dist + 1 == s) < times[nx][ny] && vis[nx][ny]==-1) {
vis[nx][ny] = dist + (dist + 1 == s);
q.push({nx, ny});
if (make_pair(nx, ny) == en) return 1;
}
}
}
return 0;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> s;
queue<pair<int, int>> h;
for (int i = 0; i < n; i++) {
cin >> v[i];
for (int j = 0; j < n; j++) {
times[i][j] = (int)1e9;
if (v[i][j] == 'M') st = {i, j};
if (v[i][j] == 'H') {
h.push({i, j});
times[i][j] = 0;
}
if (v[i][j] == 'D') en = {i, j};
}
}
while (h.size() > 0) {
int x = h.front().first, y = h.front().second;
h.pop();
for (int d = 0; d < 4; d++) {
int nx = x + dx[d], ny = y + dy[d];
if (valid(nx, ny) && times[x][y] + 1 < times[nx][ny]) {
times[nx][ny] = times[x][y] + 1;
h.push({nx, ny});
}
}
}
int l = -1, r = n * n;
while (l + 1 < r) {
int m = (l + r) / 2;
if (check(m)) l = m;
else r = m;
}
cout << l;
}
