#include <bits/stdc++.h>
#define ll long long
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
#define si set<int>
#define vvi vector<vector<int>>
#define vvl vector<vector<long long>>
#define vl vector<long long>
#define pii pair<int, int>
#define pll pair<ll,ll>
#define add push_back
#define REP(i,a) for (int i = 0; i < (a); i++)
using namespace std;
template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;
const int INF = 1005000000;
//const ll MOD = 1000000007LL;
const ll MOD = 998244353LL;
int ni() {
int x; cin >> x;
return x;
}
ll nl() {
ll x; cin >> x;
return x;
}
double nd() {
double x; cin >> x;
return x;
}
string next() {
string x; cin >> x;
return x;
}
int N,S;
char grid[800][800];
pii mecho1;
pii mecho2;
vector<pii> hives;
vvi dirs = {{-1,0},{1,0},{0,-1},{0,1}};
void printDist(vvi dist) {
REP(i,N) REP(j,N) {
if (dist[i][j]==INF)
cout << "I";
else
cout << dist[i][j];
if (j==N-1) cout << '\n';
}
}
bool solve(int headstart) {
vvi mechoDist(N,vi(N,INF));
queue<pii> mechoQ;
mechoDist[mecho1.first][mecho1.second] = 0;
mechoQ.push(mecho1);
vvi beeDist(N,vi(N,INF));
queue<pii> beeQ;
for (pii& hive: hives) {
beeDist[hive.first][hive.second] = 0;
beeQ.push(hive);
}
while (!beeQ.empty()) {
pii p = beeQ.front();
if (beeDist[p.first][p.second] == headstart) break;
beeQ.pop();
for (vi& dir: dirs) {
int newR = p.first+dir[0];
int newC = p.second+dir[1];
if (newR >= 0 && newR < N && newC >= 0 && newC < N && beeDist[newR][newC]==INF && grid[newR][newC] != 'T' && grid[newR][newC] != 'D') {
beeDist[newR][newC] = beeDist[p.first][p.second]+1;
beeQ.push({newR,newC});
}
}
}
int travel = 0;
while (!mechoQ.empty()) {
travel += S;
//mecho moves up to travel spaces from the origin.
while (!mechoQ.empty()) {
pii p = mechoQ.front();
if (mechoDist[p.first][p.second] == travel) break;
mechoQ.pop();
if (beeDist[p.first][p.second] < INF) {
//bees control this cell already
continue;
}
for (vi& dir: dirs) {
int newR = p.first+dir[0];
int newC = p.second+dir[1];
if (newR >= 0 && newR < N && newC >= 0 && newC < N && mechoDist[newR][newC]==INF && grid[newR][newC] != 'T' && grid[newR][newC] != 'H' && beeDist[newR][newC] == INF) {
mechoDist[newR][newC] = mechoDist[p.first][p.second]+1;
mechoQ.push({newR,newC});
}
}
}
headstart++;
while (!beeQ.empty()) {
pii p = beeQ.front();
if (beeDist[p.first][p.second] == headstart) break;
beeQ.pop();
for (vi& dir: dirs) {
int newR = p.first+dir[0];
int newC = p.second+dir[1];
if (newR >= 0 && newR < N && newC >= 0 && newC < N && beeDist[newR][newC]==INF && grid[newR][newC] != 'T' && grid[newR][newC] != 'D') {
beeDist[newR][newC] = beeDist[p.first][p.second]+1;
beeQ.push({newR,newC});
}
}
}
}
if (mechoDist[mecho2.first][mecho2.second] < INF) {
//he can reach his home!
return true;
} else {
return false;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
N = ni();
S = ni();
REP(i,N) {
string s = next();
REP(j,N) {
grid[i][j] = s[j];
if (grid[i][j]=='M')
mecho1 = {i,j};
else if (grid[i][j]=='D')
mecho2 = {i,j};
else if (grid[i][j]=='H')
hives.add({i,j});
}
}
int lo = 0;
int hi = N*N;
if (!solve(0)) {
//mecho can't reach the house ever
cout << -1;
return 0;
}
while (lo < hi) {
int m = (lo+hi+1)/2;
if (solve(m)) {
lo = m;
} else {
hi = m-1;
}
}
cout << lo;
}
