#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i<n;i++)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(),v.rend()
#define pb push_back
#define sz(a) (int)a.size()
#define int long long
const int N = 805;
char c[N][N];
int n, s;
bool ok(int i, int j) {
return (i >= 0 && j >= 0 && i < n && j < n && c[i][j] != 'T' && c[i][j] != 'H');
}
vector<vector<int>> bfs(vector<pair<int,int>> nodes, char forbidden) {
vector<vector<int>> dist(n, vector<int>(n, INT_MAX));
queue<pair<int,int>> q;
for(auto f: nodes) {
dist[f.first][f.second] = 0;
q.push({f.first, f.second});
}
while(!q.empty()) {
int i = q.front().first, j = q.front().second;
q.pop();
if(ok(i + 1, j) && c[i + 1][j] != forbidden && dist[i + 1][j] == INT_MAX) {
dist[i + 1][j] = dist[i][j] + 1;
q.push({i + 1, j});
}
if(ok(i - 1, j) && c[i - 1][j] != forbidden && dist[i - 1][j] == INT_MAX) {
dist[i - 1][j] = dist[i][j] + 1;
q.push({i - 1, j});
}
if(ok(i, j + 1) && c[i][j + 1] != forbidden && dist[i][j + 1] == INT_MAX) {
dist[i][j + 1] = dist[i][j] + 1;
q.push({i, j + 1});
}
if(ok(i, j - 1) && c[i][j - 1] != forbidden && dist[i][j - 1] == INT_MAX) {
dist[i][j - 1] = dist[i][j] + 1;
q.push({i, j - 1});
}
}
return dist;
}
vector<vector<int>> bees;
bool dfs(int startx, int starty, int val) {
queue<pair<pair<int, int>, int>> q;
q.push({{startx, starty}, 0});
if(val >= bees[startx][starty]) return false;
vector<vector<int>> dist(n, vector<int>(n, -1));
dist[startx][starty] = val;
while(!q.empty()) {
int i = q.front().first.first, j = q.front().first.second, moves = q.front().second;
q.pop();
if(c[i][j] == 'D') return true;
if(ok(i + 1, j) && dist[i + 1][j] == -1 && (dist[i][j] + ((moves + 1) % s == 0)) < bees[i + 1][j]) {
dist[i + 1][j] = dist[i][j] + ((moves + 1) % s == 0);
q.push({{i + 1, j}, moves + 1});
}
if(ok(i - 1, j) && dist[i - 1][j] == -1 && (dist[i][j] + ((moves + 1) % s == 0)) < bees[i - 1][j]) {
dist[i - 1][j] = dist[i][j] + ((moves + 1) % s == 0);
q.push({{i - 1, j}, moves + 1});
}
if(ok(i, j + 1) && dist[i][j + 1] == -1 && (dist[i][j] + ((moves + 1) % s == 0)) < bees[i][j + 1]) {
dist[i][j + 1] = dist[i][j] + ((moves + 1) % s == 0);
q.push({{i, j + 1}, moves + 1});
}
if(ok(i, j - 1) && dist[i][j - 1] == -1 && (dist[i][j] + ((moves + 1) % s == 0)) < bees[i][j - 1]) {
dist[i][j - 1] = dist[i][j] + ((moves + 1) % s == 0);
q.push({{i, j - 1}, moves + 1});
}
}
return false;
}
void solve() {
cin >> n >> s;
int startx, starty;
vector<pair<int,int>> f;
for(int i = 0;i < n; ++i) {
for(int j = 0;j < n; ++j) {
cin >> c[i][j];
if(c[i][j] == 'M') {
startx = i, starty = j;
}
if(c[i][j] == 'H') {
f.pb({i, j});
}
}
}
bees = bfs(f, 'D');
int l = 0, r = 1e9;
int ans = -1;
while(l <= r) {
int mid = l + r >> 1;
if(dfs(startx, starty, mid)) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
cout << ans << "\n";
}
int32_t main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t = 1;
//cin >> t;
while(t--) {
solve();
}
}
