#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define vc vector<char>
#define vi vector<int>
#define vii vector<vi>
#define viii vector<vii>
#define viiii vector<viii>
#define viiiii vector<viiii>
#define vb vector<bool>
#define vbb vector<vb>
#define pi pair<int, int>
#define ppi pair<pair<int, int>, int>
#define pip pair<int, pair<int, int>>
#define endl '\n'
#define PI acos(-1)
#define all(vec) vec.begin(), vec.end()
#define Point pair<pair<int, int>, pair<int, int>>
#define X first.first
#define Y first.second
#define C second.first
#define T second.second
// mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
// uniform_int_distribution<int> dist(l, r);
const int mod = 1e9 + 7;
const int maxn = 22;
const int p1 = 911382323;
const int p2 = 496719319;
const int maxval = 128;
const double eps = 1e-9;
const int S = 550;
const int inf = 1e15;
int n, s;
vector<pi> adjacent(pi p, vector<vc>& grid) {
vector<pi> pos = {
{p.first-1, p.second},
{p.first+1, p.second},
{p.first, p.second-1},
{p.first, p.second+1}
};
vector<pi> res;
for (pi p2 : pos) {
if (p2.first < 0 || p2.first >= n || p2.second < 0 || p2.second >= n || grid[p2.first][p2.second] == 'T') continue;
res.push_back(p2);
}
return res;
}
bool isPossible(int delay, vector<vc>& grid, vii& distbees) {
queue<pi> q;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 'M') q.push({i, j});
}
}
vii distbear(n+1, vi(n+1, INT32_MAX));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 'M') q.push({i, j});
}
}
distbear[q.front().first][q.front().second] = delay * s;
while (!q.empty()) {
pi p = q.front();
q.pop();
if (distbear[p.first][p.second]/s >= distbees[p.first][p.second]) continue;
for (pi to : adjacent(p, grid)) {
if (distbear[to.first][to.second] < INT32_MAX || ((distbear[p.first][p.second])/s) >= distbees[to.first][to.second]) continue;
distbear[to.first][to.second] = distbear[p.first][p.second] + 1;
q.push(to);
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 'D') return distbear[i][j] < INT32_MAX;
}
}
}
void solve() {
cin >> n >> s;
vector<vc> grid(n+1, vc(n+1));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) cin >> grid[i][j];
}
vector<pi> hives;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 'H') hives.push_back({i, j});
}
}
queue<pi> q;
vii dist(n+1, vi(n+1, INT32_MAX));
for (pi p : hives) {
dist[p.first][p.second] = 0;
q.push(p);
}
while (!q.empty()) {
pi p = q.front();
q.pop();
for (pi to : adjacent(p, grid)) {
if (dist[to.first][to.second] < INT32_MAX || grid[to.first][to.second] == 'D') continue;
dist[to.first][to.second] = dist[p.first][p.second] + 1;
q.push(to);
}
}
int l = 0, r = 1e9;
while (r-l>1) {
int m = (l+r)/2;
if (isPossible(m, grid, dist)) l = m;
else r = m;
}
if (!isPossible(l, grid, dist)) cout << -1 << endl;
else cout << l << endl;
}
/*
*/
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
bool test = 0;
int t;
if (test) cin >> t;
else t = 1;
while (t--) solve();
return 0;
}
