#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <unordered_set>
#include <map>
#include <string>
#include <tuple>
#include <numeric>
#include <climits>
#include <bitset>
#include <iomanip>
#include <random>
#include <ctime>
using namespace std;
typedef long long ll;
const ll INF = 1e14;
const ll MOD = 1e9 + 7;
const ll MAXN = 2e5 + 1;
ll fact[MAXN];
void precompute()
{
fact[0] = 1;
for (ll i = 1; i < MAXN; i++) {
fact[i] = (i * fact[i - 1]) % MOD;
}
}
ll powmod(ll a, ll b){
a %= MOD;
if (a == 0) return 0;
ll product = 1;
while(b > 0){
if (b&1){ // you can also use b % 2 == 1
product *= a;
product %= MOD;
--b;
}
a *= a;
a %= MOD;
b /= 2; // you can also use b >> 1
}
return product;
}
ll max(ll a, ll b) {
if (a > b) {
return a;
} else {
return b;
}
}
ll min(ll a, ll b) {
if (a < b) {
return a;
} else {
return b;
}
}
//calculates the inverse of a number mod MOD
ll inv(ll a) {
return powmod(a, MOD - 2);
}
struct State{
ll cr, cc, cd;
};
ll dr[4] = {0, 1, 0, -1};
ll dc[4] = {1, 0, -1, 0};
void solve(ll ca) {
ll n, s;
cin >> n >> s;
char grid[n][n];
pair<ll, ll> sc;
for (ll i = 0; i < n; i++) {
for (ll j = 0; j < n; j++) {
cin >> grid[i][j];
if (grid[i][j] == 'M') {
sc = {i, j};
}
}
}
ll dist[n][n];
for (ll i = 0; i < n; i++) {
for (ll j = 0; j < n; j++) {
dist[i][j] = INF;
}
}
queue<State> q;
for (ll i = 0; i < n; i++) {
for (ll j = 0; j < n; j++) {
if (grid[i][j] == 'H') {
q.push({i, j, 0});
}
}
}
while (!q.empty()) {
State cur = q.front();
q.pop();
if (dist[cur.cr][cur.cc] <= cur.cd) {
continue;
}
dist[cur.cr][cur.cc] = cur.cd;
for (ll k = 0; k < 4; k++) {
ll nr = cur.cr + dr[k];
ll nc = cur.cc + dc[k];
if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] != 'T' && grid[nr][nc] != 'D' && grid[nr][nc] != 'H') {
q.push({nr, nc, cur.cd+1});
}
}
}
/*
for (ll i = 0; i < n; i++) {
for (ll j = 0; j < n; j++) {
if (dist[i][j] == INF) {
cout << -1 << " ";
continue;
}
cout << dist[i][j] << " ";
}
cout << endl;
}*/
ll lo = 0; ll hi = INF;
lo--;
while (lo < hi) {
ll mid = lo + (hi - lo + 1)/2;
//mid = 2;
bool works = false;
bool visited[n][n];
for (ll i = 0; i < n; i++) {
for (ll j = 0; j < n; j++) {
visited[i][j] = false;
}
}
queue<State> q2;
q2.push({sc.first, sc.second, s*mid});
while (!q2.empty()) {
State cur = q2.front();
q2.pop();
/*if (cur.cr == 3 && cur.cc == 6) {
cout << "I AM HERE" << endl;
}*/
if (grid[cur.cr][cur.cc] == 'D') {
works = true;
break;
}
/*if (cur.cr == 3 && cur.cc == 6) {
cout << "I AM HERE" << endl;
}*/
ll nummin = cur.cd/s;
if (nummin >= dist[cur.cr][cur.cc]) {
continue;
}
if (visited[cur.cr][cur.cc]) {
continue;
}
//cout << cur.cr << " " << cur.cc << endl;
visited[cur.cr][cur.cc] = true;
for (ll k = 0; k < 4; k++) {
ll nr = cur.cr + dr[k];
ll nc = cur.cc + dc[k];
if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] != 'T') {
q2.push({nr, nc, cur.cd+1});
}
}
}
if (works) {
lo = mid;
} else {
hi = mid - 1;
}
/*cout << works << endl;
return;*/
}
cout << lo << endl;
}
int main() {
mt19937 rng(0);
// Fast IO
ios::sync_with_stdio(false);
cin.tie(nullptr);
/*
freopen("gravity.in", "r", stdin);
freopen("gravity.out", "w", stdout);
*/
ll t = 1;
//cin >> t;
ll co = 0;
while (t--) {
solve(co);
co++;
}
}
