#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using il = pair<ll, ll>;
#define foru(i, l, r) for(int i=(l); i<=(r); ++i)
#define ford(i, l, r) for(int i=(l); i>=(r); --i)
#define fore(x, v) for(auto &x : v)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
void setIO(string name) {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (!name.empty()) {
freopen((name + ".in").c_str(), "r", stdin);
freopen((name + ".out").c_str(), "w", stdout);
}
}
const int dx[] = {0, 0, -1, 1}, dy[] = {-1, 1, 0, 0};
const int LIM = 1e9;
const int N = 808;
int n, s, vi[N][N];
ii st, en;
vector<ii> hives;
char a[N][N];
bool e(int i, int j) { return i >= 1 && i <= n && j >= 1 && j <= n; }
void propaganda(vector<ii> &lst, int xet, int dis) {
queue<pair<ii, int>> bfs;
for(auto x : lst) bfs.push({x, 0});
lst.clear();
while (!bfs.empty()) {
auto at = bfs.front(); bfs.pop();
int x = at.fi.fi, y = at.fi.se;
if (vi[x][y] == 2 && xet == 1) {
continue;
}
if (at.se == dis) {
lst.emplace_back(at.fi);
continue;
}
foru(d, 0, 3) {
int nx = x+dx[d], ny = y+dy[d];
if (!e(nx, ny) || a[nx][ny] == 'T') continue;
if (xet == 2 && a[nx][ny] == 'D') continue;
if (vi[nx][ny] != 0) {
if (xet == 1) continue;
if (vi[nx][ny] == 2) continue;
}
vi[nx][ny] = xet;
bfs.push({{nx, ny}, at.se+1});
}
}
}
void out() {
foru(i, 1, n) {
foru(j, 1, n) cout << vi[i][j] << " ";
cout << "\n";
}
cout << "---------\n";
}
bool can(int eat_time) {
memset(vi, 0, sizeof(vi));
vector<ii> me, bees;
me.emplace_back(st);
bees = hives;
propaganda(bees, 2, eat_time);
while (!me.empty()) {
propaganda(me, 1, s);
propaganda(bees, 2, 1);
}
return vi[en.fi][en.se] == 1;
}
int main() {
setIO("");
cin >> n >> s;
foru(i, 1, n)
foru(j, 1, n) {
cin >> a[i][j];
if (a[i][j] == 'M') st = {i, j};
else if (a[i][j] == 'D') en = {i, j};
else if (a[i][j] == 'H') hives.emplace_back(i, j);
}
int ans = -1;
for(int z=n*n; z>0; z>>=1)
while (ans+z <= n*n && can(ans+z))
ans += z;
cout << ans;
}
