#include<bits/stdc++.h>
using namespace std;
const int maxn = 805;
const int INF = 1e9;
const pair<int, int> mv[4] = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
int n, s;
char board[maxn][maxn];
bool inb(int a, int b){
return a >= 1 && a <= n && b >= 1 && b <= n;
}
bool chk(int a, int b){
return inb(a, b) && board[a][b] != 'D' && board[a][b] != 'T';
}
int dm[maxn][maxn], db[maxn][maxn];
int val[maxn][maxn];
vector<pair<int, int>> pq[maxn*maxn];
bool chk(int dist){
queue<pair<int, int>> q;
memset(dm, -1, sizeof(dm));
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++)if(board[i][j] == 'M'){
dm[i][j] = 0;
q.push({i, j});
}
}
while(!q.empty()){
auto x = q.front();
q.pop();
if(dm[x.first][x.second]/s + dist >= db[x.first][x.second])continue;
for(auto v: mv){
int nx = x.first + v.first, ny = x.second + v.second;
if(inb(nx, ny) && board[nx][ny] == 'D')return true;
if(dm[nx][ny] == -1 && chk(nx, ny)){
dm[nx][ny] = dm[x.first][x.second] + 1;
q.push({nx, ny});
}
}
}
return false;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> s;
queue<pair<int, int>> q;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
cin >> board[i][j];
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(board[i][j] == 'H')q.push({i, j});
else db[i][j] = INF;
}
}
while(!q.empty()){
auto x = q.front();
q.pop();
for(auto v: mv){
int nx = x.first + v.first, ny = x.second + v.second;
if(db[nx][ny] == INF && chk(nx, ny)){
db[nx][ny] = db[x.first][x.second] + 1;
q.push({nx, ny});
}
}
}
int l = -1, r = maxn*maxn;
while(l < r){
int mid = (l+r+1)>>1;
if(chk(mid))l = mid;
else r = mid - 1;
}
cout << l;
}
