#include <bits/stdc++.h>
typedef long long int ll;
#define INF (1e9 + 7)
#define INF2 (998244353)
#define N (ll)5e4+5
using namespace std;
int n, s, mx, my, dx, dy;
bool bb=0;
char a[802][802];
int d[802][802], d2[802][802];
vector<pair<int, int>> v;
void bfs(pair<int, int> p){
queue<pair<int ,int>> q;
pair<int, int> p2;
int t;
q.push(p);
while(!q.empty()){
p2 = q.front();
q.pop();
if(p2.first == dx && p2.second == dy)continue;
t = d[p2.first][p2.second];
if(p2.first > 1 && d[p2.first - 1][p2.second] > t + 1 && a[p2.first - 1][p2.second]!='T'){
q.push({p2.first-1, p2.second});
d[p2.first - 1][p2.second] = t + 1;
}
if(p2.second > 1 && d[p2.first][p2.second - 1] > t + 1 && a[p2.first][p2.second - 1]!='T'){
q.push({p2.first, p2.second - 1});
d[p2.first][p2.second - 1] = t + 1;
}
if(p2.first < n && d[p2.first + 1][p2.second] > t + 1 && a[p2.first + 1][p2.second]!='T'){
q.push({p2.first+1, p2.second});
d[p2.first + 1][p2.second] = t + 1;
}
if(p2.second < n && d[p2.first][p2.second + 1] > t + 1 && a[p2.first][p2.second + 1]!='T'){
q.push({p2.first, p2.second + 1});
d[p2.first][p2.second + 1] = t + 1;
}
}
}
void bfs2(int mid){
queue<pair<int ,int>> q;
pair<int, int> p2;
int t;
q.push({mx, my});
while(!q.empty()){
p2 = q.front();
q.pop();
t = d2[p2.first][p2.second];
if(p2.first == dx + 1 && p2.second == dy){
bb = 1;
return;
}
if(p2.first == dx - 1 && p2.second == dy){
bb = 1;
return;
}
if(p2.first == dx && p2.second == dy - 1){
bb = 1;
return;
}
if(p2.first == dx && p2.second == dy + 1){
bb = 1;
return;
}
if(p2.first > 1 && d2[p2.first - 1][p2.second] > t + 1 && a[p2.first - 1][p2.second]!='T' && (t + 1)/s + mid < d[p2.first - 1][p2.second]){
q.push({p2.first-1, p2.second});
d2[p2.first - 1][p2.second] = t + 1;
}
if(p2.second > 1 && d2[p2.first][p2.second - 1] > t + 1 && a[p2.first][p2.second - 1]!='T' && (t + 1)/s + mid < d[p2.first][p2.second - 1]){
q.push({p2.first, p2.second - 1});
d2[p2.first][p2.second - 1] = t + 1;
}
if(p2.first < n && d2[p2.first + 1][p2.second] > t + 1 && a[p2.first + 1][p2.second]!='T' && (t + 1)/s + mid < d[p2.first + 1][p2.second]){
q.push({p2.first+1, p2.second});
d2[p2.first + 1][p2.second] = t + 1;
}
if(p2.second < n && d2[p2.first][p2.second + 1] > t + 1 && a[p2.first][p2.second + 1]!='T' && (t + 1)/s + mid < d[p2.first][p2.second + 1]){
q.push({p2.first, p2.second + 1});
d2[p2.first][p2.second + 1] = t + 1;
}
}
}
void solve(){
cin >> n >> s;
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
d[i][j] = INF;
}
}
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
cin >> a[i][j];
if(a[i][j] == 'H'){
v.push_back({i, j});
d[i][j] = 0;
}
if(a[i][j] == 'M'){
mx = i;
my = j;
}
if(a[i][j] == 'D'){
dx = i;
dy = j;
}
}
}
for(auto u : v){
bfs(u);
}
d2[mx][my] = 0;
int l=0, r=d[mx][my]-1, mid, ans=-1;
while(r >= l){
mid = (r+l)/2;
bb = 0;
memset(d2, INF, sizeof(d2));
d2[mx][my] = 0;
bfs2(mid);
if(bb){
ans = mid;
l = mid + 1;
}
else{
r = mid - 1;
}
}
cout<<ans;
}
int main(){
//freopen("gravity.in", "r", stdin);
//freopen("gravity.out", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
int T = 1;
//cin>>T;
while (T--){
solve();
}
}
