#include "bits/stdc++.h"
using namespace std;
const int maxn = 805;
char s[maxn][maxn];
int n, S;
int vis[maxn][maxn], dis[maxn][maxn], dis1[maxn][maxn];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
int sx, sy, fx, fy;
void precalc(){
using pii = pair<int, pair<int, int>>;
priority_queue<pii, vector<pii>, greater<pii>> q;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
dis[i][j] = n * n;
if(s[i][j] == 'H'){
q.push({0, {i, j}});
dis[i][j] = 0;
}
}
}
while(!q.empty()){
pii src = q.top();
q.pop();
for(int i = 0; i < 4; ++i){
int newx = src.second.first + dx[i], newy = src.second.second + dy[i];
if(newx <= n && newx > 0 && newy <= n && newy > 0){
if(dis[src.second.first][src.second.second] + 1 < dis[newx][newy] && s[newx][newy] != 'T' && s[newx][newy] != 'D'){
dis[newx][newy] = dis[src.second.first][src.second.second] + 1;
q.push({dis[newx][newy], {newx, newy}});
}
}
}
}
}
bool can(int x){
queue<pair<int, int>> q;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
dis1[i][j] = n * n;
if(s[i][j] == 'T')vis[i][j] = 1;
else if(s[i][j] == 'M'){
vis[i][j] = 1;
dis1[i][j] = 0;
q.push({i, j});
}else {
vis[i][j] = 0;
}
}
}
while(!q.empty()){
pair<int, int> src = q.front();
q.pop();
for(int i = 0; i < 4; ++i){
int newx = src.first + dx[i], newy = src.second + dy[i];
if(newx <= n && newx > 0 && newy <= n && newy > 0){
if(s[newx][newy] != 'T' && !vis[newx][newy]){
int cost = (dis1[src.first][src.second] + 1) / S + x;
if(cost < dis[newx][newy]){
vis[newx][newy] = 1;
dis1[newx][newy] = dis1[src.first][src.second] + 1;
q.push({newx, newy});
}
}
}
}
}
if(vis[fx][fy])return 1;
return 0;
}
int main(int argc, char const *argv[])
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> S;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
cin >> s[i][j];
if(s[i][j] == 'M'){
sx = i, sy = j;
}else if(s[i][j] == 'D'){
fx = i, fy = j;
}
}
}
precalc();
int lo = 0, hi = n * n, ans = -1;
while(lo <= hi){
int mid = (lo + hi) >> 1;
if(can(mid)){
ans = mid;
lo = mid + 1;
}else {
hi = mid - 1;
}
}
cout << ans << '\n';
return 0;
}
