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