#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define endl "\n";
#define all(x) x.begin(), x.end()
const ll MOD = 1e9+7;
#define int long long
int n, s;
string grid[800];
int beeTime[800][800];
int bearTime[800][800];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
bool inside(int x, int y) {
return x >= 0 && x < n && y >= 0 && y < n;
}
int goalX, goalY;
bool works(int waitTime) {
queue<array<int, 2>> q;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
bearTime[i][j] = 1e9;
if (grid[i][j] == 'M') {
bearTime[i][j] = 0;
q.push({i, j});
}
}
}
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (inside(nx, ny) && bearTime[nx][ny] == 1e9 && grid[nx][ny] != 'T'
&& (beeTime[nx][ny] * s > bearTime[x][y] + 1 + waitTime * s || grid[nx][ny] == 'D')) {
bearTime[nx][ny] = bearTime[x][y] + 1;
q.push({nx, ny});
}
}
}
return bearTime[goalX][goalY] != 1e9;
}
void solve() {
cin >> n >> s;
for (int i = 0; i < n; i++) {
cin >> grid[i];
}
queue<pair<int, int>> q;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
beeTime[i][j] = 1e9;
if (grid[i][j] == 'H') {
q.push({i, j});
beeTime[i][j] = 0;
}
if (grid[i][j] == 'D') {
goalX = i;
goalY = j;
}
}
}
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (inside(nx, ny) && beeTime[nx][ny] == 1e9 && grid[nx][ny] != 'T') {
beeTime[nx][ny] = beeTime[x][y] + 1;
q.push({nx, ny});
}
}
}
int l = 0, r = 1e6;
int ans = -1;
while (l <= r) {
int mid = (l + r) / 2;
if (works(mid)) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
cout << ans << endl;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
//freopen("example.in", "r", stdin);
//freopen("atlarge.out", "w", stdout);
int t = 1; // cin >> t;
while (t--) {
solve();
}
}
