/*=======================================
Build : LOCAL / Debug
Compiler : g++ -std=gnu++17
Note: read problem twice ฅ(^>⩊<^) ฅ
=======================================*/
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#include "debug.hpp"
#else
#define debug(...) ((void)0)
#endif
#define sz(v) ((int)((v).size()))
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using ll = int64_t;
using db = long double;
template<typename T, size_t SZ> using ar = array<T, SZ>;
const int mxN = (int)2e5+5;
const int xdir[4]{1,0,-1,0}, ydir[4]{0,1,0,-1};
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;
template<typename T> int lwb(const vector<T>& a, const T& x){
return lower_bound(a.begin(), a.end(), x) - a.begin(); }
template<typename T> int upb(const vector<T>& a, const T& x){
return upper_bound(a.begin(), a.end(), x) - a.begin(); }
constexpr int pct(int x) { return __builtin_popcount(x); } // # of bits set
constexpr int ctz(int x) { // assert(x >= 0);
return x == 0 ? -1 : __builtin_ctz(x); } // # of trailing zeros
constexpr int bits(int x) { // assert(x >= 0);
return x == 0 ? 0 : 31-__builtin_clz(x); } // floor(log2(x))
template<typename T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<typename T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
template<typename T, typename F> T fstTrue(T lo, T hi, F f) {
assert(lo < hi); // assuming f is increasing
while (lo < hi) { // find first index such that f is true
T mid = lo+(hi-lo)/2;
f(mid) ? hi = mid : lo = mid+1;
}
return lo;
}
template<typename T, typename F> T lstTrue(T lo, T hi, F f) {
assert(lo < hi); // assuming f is decreasing
while (lo < hi) { // find first index such that f is true
T mid = lo+(hi-lo+1)/2;
f(mid) ? lo = mid : hi = mid-1;
}
return lo;
}
int64_t cdiv(int64_t a, int64_t b) {
assert(b != 0);
return a/b + ((a^b) > 0 && a % b);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, s;
cin >> n >> s;
int sx, sy;
set<pair<int,int>> home;
vector<pair<int,int>> hives;
vector<vector<char>> g(n, vector<char>(n));
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j) {
cin >> g[i][j];
if(g[i][j] == 'M') { sx = i; sy = j; }
if(g[i][j] == 'H') hives.emplace_back(i, j);
if(g[i][j] == 'D') home.insert({i, j});
}
auto valid = [&](int x, int y) {
if(x < 0 || x >= n || y < 0 || y >= n) return false;
if(g[x][y] == 'T') return false;
return true;
};
const int INF = (int)1e9;
vector<vector<int>> dist2(n, vector<int>(n, INF));
queue<pair<int,int>> q;
for(auto& [x, y]: hives) {
dist2[x][y] = 0;
q.emplace(x, y);
}
while(sz(q)) {
auto [x, y] = q.front(); q.pop();
for(int i = 0; i < 4; ++i) {
int nx = x + xdir[i];
int ny = y + ydir[i];
if(!valid(nx, ny)) continue;
if(ckmin(dist2[nx][ny], dist2[x][y] + 1))
q.emplace(nx, ny);
}
}
auto check = [&](int mid) -> bool {
if(mid >= dist2[sx][sy]) return false;
vector<vector<int>> dist(n, vector<int>(n, INF));
queue<pair<int,int>> todo;
todo.emplace(sx, sy);
dist[sx][sy] = 0;
while(sz(todo)) {
auto [x, y] = todo.front(); todo.pop();
if(home.count({x, y})) return true;
for(int i = 0; i < 4; ++i) {
int nx = x + xdir[i];
int ny = y + ydir[i];
if(!valid(nx, ny)) continue;
if(dist[nx][ny] < INF) continue;
int t = mid + (dist[x][y]+1) / s;
if(t >= dist2[nx][ny]) continue;
dist[nx][ny] = dist[x][y]+1;
todo.emplace(nx, ny);
}
}
return false;
};
cout << lstTrue(0, INF, check) << '\n';
return 0;
}
