#include <bits/stdc++.h>
#include <cstdio>
#include <ext/pb_ds/assoc_container.hpp>
#define FAST_IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define pb push_back
#define all(x) begin(x), end(x)
#define umap unordered_map
#define space " "
#define TEST_CASES int a; cin >> a; for (int i = 0; i < a; i++) {solve(); cout << endl;}
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
void solve() {
int b, c; cin >> b >> c;
vector<vector<char>> vec(b, vector<char>(b));
queue<pair<int, pair<int, int>>> q;
pair<int, int> start; pair<int, int> dest;
for (int i = 0; i < b; i++) {
for (int j = 0; j < b; j++) {
cin >> vec[i][j];
if (vec[i][j] == 'H') {
q.push({0, {i, j}});
}
if (vec[i][j] == 'M') {
start = {i, j};
}
if (vec[i][j] == 'D') {
dest = {i, j};
}
}
}
vector<vector<int>> dist(b, vector<int>(b, INT32_MAX));
while (!q.empty()) {
auto curr = q.front(); q.pop(); int x = curr.second.first; int y = curr.second.second;
if (x < 0 || y < 0 || x >= b || y >= b || curr.first > dist[x][y] || vec[x][y] == 'T' || vec[x][y] == 'D') {
continue;
}
if (x < b - 1 && dist[x + 1][y] == INT32_MAX && vec[x + 1][y] != 'T' && vec[x + 1][y] != 'D') {
q.push({curr.first + 1, {x + 1, y}});
dist[x + 1][y] = curr.first + 1;
}
if (y < b - 1 && dist[x][y + 1] == INT32_MAX && vec[x][y + 1] != 'T' && vec[x][y + 1] != 'D') {
q.push({curr.first + 1, {x, y + 1}});
dist[x][y + 1] = curr.first + 1;
}
if (x > 0 && dist[x - 1][y] == INT32_MAX && vec[x - 1][y] != 'T' && vec[x - 1][y] != 'D') {
q.push({curr.first + 1, {x - 1, y}});
dist[x - 1][y] = curr.first + 1;
}
if (y > 0 && dist[x][y - 1] == INT32_MAX && vec[x][y - 1] != 'T' && vec[x][y - 1] != 'D') {
q.push({curr.first + 1, {x, y - 1}});
dist[x][y - 1] = curr.first + 1;
}
}
int lo = 0; int hi = b * b; int res = -1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
bool flag = false;
vector<vector<bool>> visited(b, vector<bool>(b));
queue<pair<int, pair<int, int>>> q;
q.push({0, start});
while (!q.empty()) {
auto curr = q.front(); q.pop(); int x = curr.second.first; int y = curr.second.second;
if (x == dest.first && y == dest.second) {
flag = true; break;
}
if (x < 0 || y < 0 || x >= b || y >= b || vec[x][y] == 'T' || curr.first / c >= dist[x][y] - mid) {
continue;
}
if (x > 0 && !visited[x - 1][y] && vec[x - 1][y] != 'T' && (curr.first + 1) / c < dist[x - 1][y] - mid) {
q.push({curr.first + 1, {x - 1, y}});
visited[x - 1][y] = true;
}
if (y > 0 && !visited[x][y - 1] && vec[x][y - 1] != 'T' && (curr.first + 1) / c < dist[x][y - 1] - mid) {
q.push({curr.first + 1, {x, y - 1}});
visited[x][y - 1] = true;
}
if (x < b - 1 && !visited[x + 1][y] && vec[x + 1][y] != 'T' && (curr.first + 1) / c < dist[x + 1][y] - mid) {
q.push({curr.first + 1, {x + 1, y}});
visited[x + 1][y] = true;
}
if (y < b - 1 && !visited[x][y + 1] && vec[x][y + 1] != 'T' && (curr.first + 1) / c < dist[x][y + 1] - mid) {
q.push({curr.first + 1, {x, y + 1}});
visited[x][y + 1] = true;
}
}
if (flag) {
res = mid;
lo = mid + 1;
}
else {
hi = mid - 1;
}
}
cout << res;
}
int main() {
FAST_IO;
//freopen("atlarge.in", "r", stdin);
//freopen("atlarge.out", "w", stdout);
//TEST_CASES;
solve(); cout << endl;
/*int a; cin >> a;
for (int i = 1; i <= a; i++){
cout << "Case #" << i << ": ";
solve();
cout << endl;
}*/
}
