#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <chrono>
#include <string>
#include <numeric>
#include <cmath>
#include <iomanip>
#include <climits>
#include <bitset>
#define all(x) (x).begin(), (x).end()
#define vec(n) vll arr(n);
#define printarr(arr) for(auto i:arr)cout<<i<<" "; cout<<endl;
#define printdict(dict) for(auto i:dict)cout<<i.first<<": "<<i.second<<endl;
#define printadj(adj) for(ll i=0;i<n;i++){if(!adj[i].empty()){cout<<i<<": ";printarr(adj[i])}}
#define read(arr); for(ll i=0;i<arr.size();i++) cin>>arr[i];
#define readundirected(m) for(ll i=0;i<m;i++){ll a,b; cin>>a>>b; a--;b--; adj[a].pb(b);adj[b].pb(a);}
#define readdirected(m) for(ll i=0;i<m;i++){ll a,b; cin>>a>>b; a--;b--; adj[a].pb(b);}
#define readfunc(n) for(ll i=0;i<n;i++){ll a;cin>>a;a--;func_adj[i]=a;}
#define grid(n,m) for (ll i=1;i<=n;i++){for (ll j=1;j<=m;j++) cin>>graph[i][j];}
#define vll vector<ll>
#define sll set<ll>
#define msll multiset<ll>
#define qll queue<ll>
#define pll pair<ll,ll>
#define str string
#define pb push_back
#define ll long long
#define ld long double
using namespace std;
const str alph="abcdefghijklmnopqrstuvwxyz";
const str capalph="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const ll inf=2e5+1;
const ll graph_size=1000;
const ll mod=1e9+7;
const ll large=1e18;
const ll small=-1e18;
// Fast Input/Output
void fastio(){
ios_base::sync_with_stdio(0);
cin.tie(nullptr);
}
// File Input/Output
str fileio(const string&filePath=__FILE__){
size_t lastSlash=filePath.find_last_of('/');
size_t lastDot=filePath.rfind('.');
return filePath.substr(lastSlash+1,lastDot-lastSlash-1);
}
// For Yes Or No Problems
str yes_or_no(bool test){
if (test){
return "YES";
}
return "NO";
}
ll n,m,q,s;
// Floodfill
char graph[graph_size+2][graph_size+2];
vector<pll> directions={{0,-1},{-1,0},{1,0},{0,1}};
bool floodfill_visited[graph_size+2][graph_size+2];
ll floodfill_bear_level[graph_size+2][graph_size+2];
pll floodfill_parent[graph_size+2][graph_size+2];
void floodfill_bear_bfs(pll coord){
for (ll i=0;i<=n+1;i++){
for (ll j=0;j<=m+1;j++){
floodfill_bear_level[i][j]=large;
floodfill_parent[i][j]={-1,-1};
floodfill_visited[i][j]=0;
}
}
ll x=coord.first;
ll y=coord.second;
queue<pll> q;
q.push({x,y});
floodfill_bear_level[x][y]=0;
while (!q.empty()){
pll curr=q.front();
q.pop();
x=curr.first;
y=curr.second;
floodfill_visited[x][y]=1;
for (auto i:directions){
if (graph[x+i.first][y+i.second]!='T' and x+i.first>=1 and x+i.first<=n and y+i.second>=1 and y+i.second<=m and floodfill_bear_level[x+i.first][y+i.second]==large){
floodfill_bear_level[x+i.first][y+i.second]=floodfill_bear_level[x][y]+1;
floodfill_parent[x+i.first][y+i.second]={x,y};
q.push({x+i.first,y+i.second});
}
}
}
}
ll floodfill_bee_level[graph_size+2][graph_size+2];
vector<pll> hives;
void floodfill_bee_bfs(){
for (ll i=0;i<=n+1;i++){
for (ll j=0;j<=m+1;j++){
floodfill_bee_level[i][j]=large;
floodfill_parent[i][j]={-1,-1};
floodfill_visited[i][j]=0;
}
}
queue<pll> q;
for (auto i:hives){
q.push(i);
floodfill_bee_level[i.first][i.second]=0;
}
while (!q.empty()){
pll curr=q.front();
q.pop();
ll x=curr.first;
ll y=curr.second;
floodfill_visited[x][y]=1;
for (auto i:directions){
if (graph[x+i.first][y+i.second]!='T' and x+i.first>=1 and x+i.first<=n and y+i.second>=1 and y+i.second<=m and floodfill_bee_level[x+i.first][y+i.second]==large){
floodfill_bee_level[x+i.first][y+i.second]=floodfill_bee_level[x][y]+1;
floodfill_parent[x+i.first][y+i.second]={x,y};
q.push({x+i.first,y+i.second});
}
}
}
}
bool graph1[graph_size+2][graph_size+2];
ll floodfill_ans_level[graph_size+2][graph_size+2];
void floodfill_ans_bfs(pll coord,ll t){
for (ll i=0;i<=n+1;i++){
for (ll j=0;j<=m+1;j++){
floodfill_ans_level[i][j]=large;
floodfill_parent[i][j]={-1,-1};
floodfill_visited[i][j]=0;
}
}
ll x=coord.first;
ll y=coord.second;
queue<pll> q;
q.push({x,y});
floodfill_ans_level[x][y]=0;
while (!q.empty()){
pll curr=q.front();
q.pop();
x=curr.first;
y=curr.second;
floodfill_visited[x][y]=1;
for (auto i:directions){
if (graph[x+i.first][y+i.second]!='T' and (floodfill_ans_level[x][y]+1)/s+t<floodfill_bee_level[x+i.first][y+i.second] and x+i.first>=1 and x+i.first<=n and y+i.second>=1 and y+i.second<=m and floodfill_ans_level[x+i.first][y+i.second]==large){
floodfill_ans_level[x+i.first][y+i.second]=floodfill_ans_level[x][y]+1;
floodfill_parent[x+i.first][y+i.second]={x,y};
q.push({x+i.first,y+i.second});
}
}
}
}
// Binary Search
pll home,bear;
bool check(ll t){
if (t>=floodfill_bee_level[bear.first][bear.second]){
return 0;
}
floodfill_ans_bfs(bear,t);
bool test=0;
for (auto i:directions){
test=max(test,floodfill_visited[home.first+i.first][home.second+i.second]);
}
return test;
}
// Returns the first value in the range such that check(value)=True.
ll first_true(ll low,ll high){
while (low<high){
ll mid=(low+high)/2;
if (check(mid)){
high=mid;
}
else{
low=mid+1;
}
}
return low;
}
// Returns the last value in the range such that check(value)=True.
ll last_true(ll low,ll high){
while (low<high){
ll mid=(low+high+1)/2;
if (check(mid)){
low=mid;
}
else{
high=mid-1;
}
}
return low;
}
int main(){
// auto start_time=chrono::steady_clock::now();
fastio();
// str filename=fileio();
// ifstream cin(filename+".in");
// ofstream cout(filename+".out");
ll t=1;
// cin>>t;
while (t--){
cin>>n>>s;
m=n;
grid(n,m);
for (ll i=1;i<=n;i++){
for (ll j=1;j<=m;j++){
if (graph[i][j]=='H'){
hives.pb({i,j});
}
if (graph[i][j]=='M'){
bear={i,j};
}
if (graph[i][j]=='D'){
home={i,j};
}
}
}
floodfill_bear_bfs(bear);
floodfill_bee_bfs();
// for (ll i=0;i<=n+1;i++){
// for (ll j=0;j<=m+1;j++){
// if (floodfill_bear_level[i][j]!=large){
// // ld val=floodfill_bear_level[i][j];
// // val/=s;
// // floodfill_bear_level[i][j]=ceil(val);
// floodfill_bear_level[i][j]/=s;
// }
// }
// }
// for (ll i=1;i<=n;i++){
// for (ll j=1;j<=m;j++){
// if (floodfill_bear_level[i][j]==large) cout<<-1<<" ";
// else cout<<floodfill_bear_level[i][j]<<" ";
// }
// cout<<"\n";
// }
// cout<<"\n";
// for (ll i=1;i<=n;i++){
// for (ll j=1;j<=m;j++){
// if (floodfill_bee_level[i][j]==large) cout<<-1<<" ";
// else cout<<floodfill_bee_level[i][j]<<" ";
// }
// cout<<"\n";
// }
// cout<<"\n";
ll ans=last_true(0,n+m);
if (!check(0)){
ans--;
}
cout<<ans<<"\n";
}
// auto end_time=chrono::steady_clock::now();
// auto elapsed_time=chrono::duration_cast<chrono::milliseconds>(end_time-start_time);
// cout<<"Elapsed time: "<<elapsed_time.count()<<" milliseconds\n";
}
