#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <map>
#include <climits>
#include <cmath>
#include <algorithm>
#include <stack>
using namespace std;
#define speedup ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define ll long long
const ll MAXN = 810;
ll bee[MAXN][MAXN];
ll dist[MAXN][MAXN];
//pair<ll,ll> parent[MAXN][MAXN];
bool vis[MAXN][MAXN];
ll dX[] = {1, -1, 0, 0};
ll dY[] = {0, 0, 1, -1};
pair<ll, ll> mencho, den;
vector<string> grid;
ll n, s;
bool compute(ll k){
if (k >= bee[mencho.first][mencho.second]){
return false;
}
for (ll i = 0; i < MAXN; i++){
for (ll j = 0; j < MAXN; j++){
dist[i][j] = 1e9;
//parent[i][j] = {-1, -1};
vis[i][j] = false;
}
}
queue<pair<ll, ll>> q;
q.push(mencho);
dist[mencho.first][mencho.second] = 0;
while (!q.empty()){
ll x = q.front().first, y = q.front().second; q.pop();
vis[x][y] = true;
if (make_pair(x, y) == den){
break;
}
for (ll i = 0; i < 4; i++){
ll nX = x + dX[i], nY = y+dY[i];
bool b1 = nX < 0 || nX >= n || nY < 0 || nY >= n;
if (b1){
continue;
}
bool b2 = grid[nX][nY] == 'T' || grid[nX][nY] == 'H' || grid[nX][nY] == 'D';
if (b2){
continue;
}
/*if (nX < 0 || nX >= n || nY < 0 || nY >= n || grid[nX][nY] == 'T' || grid[nX][nY] == 'H' || grid[nX][nY] == 'D'){
continue;
}*/
ll cur_time = (dist[x][y] + 1) / s;
if (!vis[nX][nY]) {
if ((dist[nX][nY] > dist[x][y] + 1) && ((bee[nX][nY] - k) > cur_time)) {
dist[nX][nY] = dist[x][y] + 1;
//parent[nX][nY] = {x, y};
q.push({nX, nY});
}
}
}
}
for (int i = 0; i < 4; i++){
ll nX = den.first+dX[i], nY = den.second+dY[i];
bool b1 = nX < 0 || nX >= n || nY < 0 || nY >= n;
if (b1) {
continue;
}
bool b2 = grid[nX][nY] == 'T' || grid[nX][nY] == 'H';
if (b2){
continue;
}
/*if (nX < 0 || nX >= n || nY < 0 || nY >= n || grid[nX][nY] == 'T' || grid[nX][nY] == 'H') {
continue;
}*/
ll cur_time = dist[nX][nY]/s;
if ((bee[nX][nY]-k) > cur_time){
return true;
}
}
return false;
}
int main() {
speedup
cin >> n >> s;
grid.resize(n);
vector<pair<ll, ll>> start;
for (ll i = 0; i < n; i++){
string st; cin >> st;
grid[i] = st;
for (ll j = 0; j < n; j++){
if (st[j] == 'H'){
start.push_back({i, j});
}else if (st[j] == 'M'){
mencho = {i, j};
}else if (st[j] == 'D'){
den = {i, j};
}
}
}
for (ll i = 0; i < MAXN; i++){
for (ll j = 0; j < MAXN; j++){
bee[i][j] = 1e9;
vis[i][j] = false;
}
}
queue<pair<ll, ll>> q;
for (pair<ll, ll> p: start){
bee[p.first][p.second] = 0;
q.push({p.first, p.second});
}
while (!q.empty()){
ll x = q.front().first, y = q.front().second; q.pop();
vis[x][y] = true;
for (ll i = 0; i < 4; i++){
ll nX = x + dX[i], nY = y+dY[i];
bool b1 = nX < 0 || nX >= n || nY < 0 || nY >= n;
if (b1){
continue;
}
bool b2 = grid[nX][nY] == 'T' || grid[nX][nY] == 'D';
if (b2){
continue;
}
if ((bee[nX][nY] > (bee[x][y]+1)) && !vis[nX][nY]){
bee[nX][nY] = bee[x][y]+1;
q.push({nX, nY});
}
}
}
ll l = 0, h = n*n, mid, ans = -1;
while (l <= h){
mid = (l+h)/2;
if (compute(mid)){
ans = mid;
l = mid+1;
}else{
h = mid-1;
}
}
cout << ans << endl;
return 0;
}
