#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define PI (3.141592653589)
#define M 1000000007
#define len(x) ll(x.size())
#define eb emplace_back
#define pb push_back
#define f first
#define s second
#define rep(i,j) for(int i = 0; i<j; i++)
#define rrep(i,j) for(int i = j; i>=0; i--)
#define all(x) x.begin(), x.end()
#define out(x) cout << x << endl;
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define pm cout<<"-1"<<endl
int popcnt(int x) { return __builtin_popcount(x); }
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
//Typedef
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef map<int,int> mii;
// Debug Overloads
#ifdef localenv
#define debug(x) _print(x); cerr << endl;
#else
#define debug(x)
#endif
void _print(ll t) {cerr << t;}
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(double t) {cerr << t;}
template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.f); cerr << ","; _print(p.s); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
// Operator Overloads
template<typename T> // cin >> vector<T>
istream& operator>>(istream &istream, vector<T> &v){for (auto &it : v)cin >> it;return istream;}
template<typename T> // cout << vector<T>
ostream& operator<<(ostream &ostream, const vector<T> &c) { for (auto &it : c) cout << it << " "; return ostream; }
// ********************************************** ------- CODE STARTS HERE ------- **********************************************
void solve(){
int n,s;
cin >> n >> s;
vector<string> a(n);
pi start,end;
queue<pi> q;
//min seconds to reach [i][j]
vvi dist(n,vi (n,1e9));
for(int i=0;i<n;++i){
cin >> a[i];
for(int j=0;j<n;++j){
if(a[i][j] == 'M'){
start = {i,j};
} else if(a[i][j] == 'H'){
q.push({i,j});
dist[i][j] = 0;
} else if(a[i][j] == 'D'){
end = {i,j};
}
}
}
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
auto isValid = [&](int nx,int ny){
return (nx >= 0 && nx < n && ny >= 0 && ny < n);
};
while(q.size()){
auto [x,y] = q.front();
q.pop();
for(int i=0;i<4;++i){
int nx = x + dx[i],ny = dy[i] + y;
if(isValid(nx,ny) && dist[nx][ny] == 1e9 && a[nx][ny] == 'G' || a[nx][ny] == 'M'){
q.push({nx,ny});
dist[nx][ny] = dist[x][y] + 1;
}
}
}
auto check =[&](int mi) -> bool {
queue<pair<int,int>> q;
vvi distB(n,vi(n,1e5));
distB[start.first][start.second] = 0;
q.push({start.first,start.second});
while(q.size()){
auto [x,y] = q.front();
q.pop();
for(int i=0;i<4;++i){
int nx = x + dx[i],ny = y + dy[i];
if(isValid(nx,ny) && a[nx][ny] != 'T' && distB[nx][ny] == 1e5 &&((distB[x][y] + 1) / s) < (dist[nx][ny] - mi)){
q.push({nx,ny});
distB[nx][ny]=distB[x][y] + 1;
}
}
}
return distB[end.first][end.second] != 1e5;
};
int lo=0,hi=n*n;
while(lo < hi){
int mi = lo + (hi - lo+1)/2;
int ok = check(mi);
if(ok){
lo = mi;
} else{
hi = mi-1;
}
}
cout << (lo == 1e9 ? -1 : lo) << endl;
// cout << check(99999) << endl;
}
int32_t main(){
solve();
return 0;
}
