#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define db double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vll vector<long long>
#define fi first
#define se second
#define pb push_back
#define all(x) begin(x), end(x)
#define allr(x) rbegin(x), rend(x)
#define szx(x) ((int)(x).size())
#define FOR(i, a, b) for (int i = a, _b = (b); i <= _b; ++i)
#define ROF(i, a, b) for (int i = a, _b = (b); i >= _b; --i)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)
#define endl '\n'
#define inf 1000000007
#define infll 1000000000000000000
#define mod 1000000007
// #define mod 998244353
using namespace std;
using namespace __gnu_pbds;
void setIO() {
ios::sync_with_stdio(0);
cin.tie(0);
}
void openFile(string filename = "") {
if (!filename.empty())
if (ifstream(filename + ".in")) {
freopen((filename + ".in").c_str(), "r", stdin);
freopen((filename + ".out").c_str(), "w", stdout);
}
}
int n, s;
char grid[805][805];
void solve() {
vector<vector<int>> dist(n + 5, vector<int>(n + 5, 1e9));
queue<pii> q;
pii st{0, 0}, ed{0, 0};
FOR(i, 1, n) FOR(j, 1, n) {
if (grid[i][j] == 'H') q.push({i, j}), dist[i][j] = 0;
if (grid[i][j] == 'M') st = {i, j};
if (grid[i][j] == 'D') ed = {i, j};
}
while (!q.empty()) {
int x = q.front().fi, y = q.front().se;
q.pop();
int dx[]{1, 0, -1, 0};
int dy[]{0, 1, 0, -1};
REP(i, 4) {
int nx = x + dx[i], ny = y + dy[i];
if (nx < 1 || nx > n || ny < 1 || ny > n) continue;
if (grid[nx][ny] == 'T' || grid[nx][ny] == 'D') continue;
if (dist[nx][ny] != 1e9) continue;
dist[nx][ny] = dist[x][y] + 1;
q.push({nx, ny});
}
}
auto ok = [&](int t) -> bool {
while (!q.empty()) q.pop();
vector<vector<int>> d(n + 5, vector<int>(n + 5, 1e9));
q.push(st);
d[st.fi][st.se] = 0;
while (!q.empty()) {
int x = q.front().fi, y = q.front().se;
q.pop();
int dx[]{1, 0, -1, 0};
int dy[]{0, 1, 0, -1};
REP(i, 4) {
int nx = x + dx[i], ny = y + dy[i];
if (nx < 1 || nx > n || ny < 1 || ny > n) continue;
if (grid[nx][ny] == 'T') continue;
if (d[nx][ny] != 1e9) continue;
int cur = d[x][y] + 1;
if (t + cur / s < dist[nx][ny]) {
d[nx][ny] = cur;
q.push({nx, ny});
}
}
}
return d[ed.fi][ed.se] < 1e9;
};
ok(1);
int l = -1, r = dist[st.fi][st.se] + 1;
while (l + 1 < r) {
int m = (l + r) >> 1;
if (ok(m))
l = m;
else
r = m;
}
cout << l;
}
void input() {
cin >> n >> s;
FOR(i, 1, n) FOR(j, 1, n) cin >> grid[i][j];
}
void preprocess() {}
void reset() {}
int main() {
setIO();
openFile("main");
int t = 1;
// cin >> t;
preprocess();
while (t--) {
input();
solve();
reset();
}
}
