#include <bits//stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>, rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag,
tree_order_statistics_node_update>
ordered_multiset;
#define ll long long
#define iloop(m, h) for (auto i = m; i != h; i += (m < h ? 1 : -1))
#define jloop(m, h) for (auto j = m; j != h; j += (m < h ? 1 : -1))
#define kloop(m, h) for (auto k = m; k != h; k += (m < h ? 1 : -1))
#define pll pair<ll, ll>
#define INF 1000000000000000
#define MOD1 1000000007
#define MOD2 998244353
#define MOD3 1000000009
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n, m;
cin >> n >> m;
char a[n][n];
pll x, y;
ll dist[n][n];
bool vis[n][n];
queue<pll> q;
iloop(0, n) jloop(0, n) {
dist[i][j] = INF;
vis[i][j] = 0;
cin >> a[i][j];
if (a[i][j] == 'M') x = {i, j};
if (a[i][j] == 'D') y = {i, j}, vis[i][j] = 1;
if (a[i][j] == 'T') vis[i][j] = 1;
if (a[i][j] == 'H') {
q.push({i, j});
dist[i][j] = 0;
vis[i][j] = 1;
}
}
while (q.size()) {
pll nd = q.front();
q.pop();
ll dst = dist[nd.first][nd.second] + 1;
if (nd.first != 0 && !vis[nd.first-1][nd.second]) {
q.push({nd.first-1, nd.second});
dist[nd.first-1][nd.second] = dst;
vis[nd.first-1][nd.second] = 1;
}
if (nd.first != n-1 && !vis[nd.first+1][nd.second]) {
q.push({nd.first+1, nd.second});
dist[nd.first+1][nd.second] = dst;
vis[nd.first+1][nd.second] = 1;
}
if (nd.second != 0 && !vis[nd.first][nd.second-1]) {
q.push({nd.first, nd.second-1});
dist[nd.first][nd.second-1] = dst;
vis[nd.first][nd.second-1] = 1;
}
if (nd.second != n-1 && !vis[nd.first][nd.second+1]) {
q.push({nd.first, nd.second+1});
dist[nd.first][nd.second+1] = dst;
vis[nd.first][nd.second+1] = 1;
}
}
ll lb = -1, ub = n*n, mid;
while (lb < ub) {
mid = (lb + ub + 1) >> 1;
bool v[n][n];
ll dd[n][n];
memset(v, 0, sizeof(v));
iloop(0, n) jloop(0, n) {
dd[i][j] = INF;
if (a[i][j] == 'T' || a[i][j] == 'M') v[i][j] = 1;
}
dd[x.first][x.second] = mid * m;
q.push({x.first, x.second});
while (q.size()) {
pll nd = q.front();
q.pop();
ll dst = dd[nd.first][nd.second] + 1;
if (nd.first != 0 && dst < dist[nd.first-1][nd.second] * m && !v[nd.first-1][nd.second]) {
q.push({nd.first-1, nd.second});
dd[nd.first-1][nd.second] = dst;
v[nd.first-1][nd.second] = 1;
}
if (nd.first != n-1 && dst < dist[nd.first+1][nd.second] * m && !v[nd.first+1][nd.second]) {
q.push({nd.first+1, nd.second});
dd[nd.first+1][nd.second] = dst;
v[nd.first+1][nd.second] = 1;
}
if (nd.second != 0 && dst < dist[nd.first][nd.second-1] * m && !v[nd.first][nd.second-1]) {
q.push({nd.first, nd.second-1});
dd[nd.first][nd.second-1] = dst;
v[nd.first][nd.second-1] = 1;
}
if (nd.second != n-1 && dst < dist[nd.first][nd.second+1] * m && !v[nd.first][nd.second+1]) {
q.push({nd.first, nd.second+1});
dd[nd.first][nd.second+1] = dst;
v[nd.first][nd.second+1] = 1;
}
}
if (v[y.first][y.second] == 1 && dd[x.first][x.second] < dist[x.first][x.second]) lb = mid;
else ub = mid - 1;
}
cout << lb;
}
