#include <bits/stdc++.h>
using namespace std;
#define A first
#define B second
#define MP make_pair
#define ms(a, x) memset(a, x, sizeof(a))
#define boost() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long double, long double> pld;
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);
const int mxN=805;
char grid[mxN][mxN];
ll dist[2][mxN][mxN];
queue <pll> q;
vector <pll> moves={{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
int n, s;
bool valid(int i, int j){
if(i >= 1 && i <= n && j >= 1 && j <= n && grid[i][j] != 'H' && grid[i][j] != 'T')
return true;
return false;
}
void bfs(){
while(!q.empty()){
pii u = q.front();
q.pop();
for(auto [x, y]:moves){
if(valid(u.A+x, u.B+y) && grid[u.A+x][u.B+y] != 'D' && dist[0][u.A+x][u.B+y] == -1){
dist[0][u.A+x][u.B+y] = dist[0][u.A][u.B]+1;
q.push({u.A+x, u.B+y});
}
}
}
}
void bfs2(ll rest){
while(!q.empty()){
pii u = q.front();
q.pop();
for(auto [x,y]:moves){
if(valid(u.A+x, u.B+y) && dist[1][u.A+x][u.B+y] == -1 && (dist[1][u.A][u.B]+1)/s < dist[0][u.A+x][u.B+y]-rest){
dist[1][u.A+x][u.B+y] = dist[1][u.A][u.B]+1;
q.push({u.A+x, u.B+y});
}
}
}
}
int main(){
ms(dist, -1);
cin >> n >> s;
pii ip, ep;
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
cin >> grid[i][j];
if(grid[i][j] == 'H'){
q.push({i, j});
dist[0][i][j]=0;
}
else if(grid[i][j] == 'M')
ip={i, j};
else if(grid[i][j] == 'D')
ep={i, j};
}
}
ll st=0, en=1e9, mid, ans=-1;
bfs();
dist[0][ep.A][ep.B] = INT_MAX;
while(st<=en){
mid = (st+en)/2;
q.push(ip);
ms(dist[1], -1);
dist[1][ip.A][ip.B]=0;
bfs2(mid);
if(dist[1][ep.A][ep.B] != -1 && mid < dist[0][ip.A][ip.B]){
ans = mid;
st = mid+1;
}
else
en = mid-1;
}
cout << ans;
}
