#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template<class T> using oset =
tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define int long long
#define vii vector<vector<int>>
#define vi vector<int>
#define v vector
#define pii pair<int, int>
#define mii map<int, int>
#define umii unordered_map<int, int>
#define si set<int>
#define usi unordered_set<int>
#define all(x) x.begin(), x.end()
#define f first
#define s second
#define endl "\n"
#define pb push_back
#define MOD 1000000007
int inf = 1e9;
char arr[801][801];
int beesTime[801][801], mechotime[801][801];
int n, s;
array<int, 2> st, des;
vii temp = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
bool isValid(int i, int j) {return i >= 1 && j >= 1 && i <= n && j <= n;}
bool isFiss(int mid)
{
queue<array<int, 2>> q;
for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) beesTime[i][j] = inf;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (arr[i][j] == 'H') {
beesTime[i][j] = 0;
q.push({i, j});
}
}
}
while (!q.empty())
{
int i = q.front()[0], j = q.front()[1];
q.pop();
for (auto x : temp)
{
int ni = i+x[0], nj = j+x[1];
if (!isValid(ni, nj) || arr[ni][nj] == 'D' || arr[ni][nj] == 'T' || beesTime[ni][nj] != inf) continue;
beesTime[ni][nj] = beesTime[i][j]+1;
q.push({ni, nj});
}
}
for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) mechotime[i][j] = inf;
if (mid < beesTime[st[0]][st[1]]) q.push(st), mechotime[st[0]][st[1]] = 0;
while (!q.empty())
{
int i = q.front()[0], j = q.front()[1]; q.pop();
for (auto x : temp)
{
int ni = i+x[0], nj = j+x[1];
if (!isValid(ni, nj) || arr[ni][nj] == 'T' || mechotime[ni][nj] != inf) continue;
if ((mid+(mechotime[i][j]+1)/s) < beesTime[ni][nj])
{
mechotime[ni][nj] = mechotime[i][j]+1;
q.push({ni, nj});
}
}
}
return mechotime[des[0]][des[1]] != inf;
}
void sol()
{
cin >> n >> s;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
cin >> arr[i][j];
if (arr[i][j] == 'M') st = {i, j};
if (arr[i][j] == 'D') des = {i, j};
}
}
int i = -1, j = n*n;
while (i < j)
{
int mid = (i+j+1)/2;
if (isFiss(mid)) {
i = mid;
}
else j = mid-1;
}
cout << i;
}
signed main(){
// #ifndef ONLINE_JUDGE
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// #endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
// cin >> t;
t = 1;
while (t--)
sol();
// cerr << "Finished" << endl;
}
