#include "bits/stdc++.h"
using namespace std;
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
struct node {
int x, y;
int mx;
int step;
int dist;
bool operator<(const node& rhs) const {
return mx < rhs.mx;
}
};
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, s;
cin >> n >> s;
vector<vector<char>> ar(n, vector<char>(n));
pair<int, int> start, end;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
cin >> ar[i][j];
if (ar[i][j] == 'M')
start = {i, j};
else if (ar[i][j] == 'D')
end = {i, j};
}
auto bee_dist_gen = [&]() {
vector<vector<int>> dist(n, vector<int>(n, 1e9));
queue<pair<int, int>> q;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (ar[i][j] == 'H')
q.push({i, j}), dist[i][j] = 0;
while (!q.empty()) {
pair<int, int> v = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int nx = v.first + dx[i], ny = v.second + dy[i];
if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
if (ar[nx][ny] == 'T') continue;
if (dist[nx][ny] <= dist[v.first][v.second] + 1) continue;
dist[nx][ny] = dist[v.first][v.second] + 1;
q.push({nx, ny});
}
}
return dist;
};
vector<vector<int>> bee_dist = bee_dist_gen();
auto test_honey = [&](int honey) {
vector<vector<bool>> vis(n, vector<bool>(n, false));
priority_queue<node> q;
q.push({start.first, start.second, bee_dist[start.first][start.second] - 1, 0, honey});
while (!q.empty()) {
node v = q.top();
q.pop();
if (vis[v.x][v.y]) continue;
vis[v.x][v.y] = true;
if (end.first == v.x && end.second == v.y)
return true;
if (v.step == 0)
v.dist++;
for (int i = 0; i < 4; i++) {
int nx = v.x + dx[i], ny = v.y + dy[i];
if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
if (ar[nx][ny] == 'T') continue;
if (bee_dist[nx][ny] < v.dist) continue;
if (vis[nx][ny]) continue;
q.push({nx, ny, min(v.mx, bee_dist[nx][ny] - v.dist), (v.step + 1) % s, v.dist});
}
}
return false;
};
int l = 0, r = 1e9;
while (l < r) {
int mid = l + (r - l + 1) / 2;
if (test_honey(mid))
l = mid;
else
r = mid - 1;
}
if (l == 1e9) l = -1;
cout << l << '\n';
}
