/* MMMMMM
MMMMMMM
MMMMMMMM .
MMMMMMMMM
HMMMMMMMMMM
MMMMMMMMMMMM M
MMMMMMMMMMMMM M
MMMMMMMMMMMMM M
MMMMMMMMMMMMM:
oMMMMMMMMMMMMMM
.MMMMMMMMMMMMMMo MMMMMMMMMMMMMMM M
MMMMMMMMMMMMMMMMMMMMMMMMMMM MMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMM. oMMMMMMMMMMMMMMM.M
MMMMMMMMMMMMMMMMMMMMMMMMMMMM MMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
oMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM: H
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM . MMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM M MMMMMM
.MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM M MMMMMMMMMM
MM. MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM M MMMMMMMMMMMM
MM MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM .MMMMMMMMMMMMMM
MM MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MM MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
.MMMMMMMMM MMMMMMMMMMMMMMMMMMMMMMMM.MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
HMMMMMMMMMMMMMMMMMMMMM.MMMMMMMMM.MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMM MMM.oMMMMMMM..MMMMMMMMM:MMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMM MM..MMMMMMM...MMMMMMM. MMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMM ..MMMMMM...MMMMMM ..MMMMMMMMMMMMMMMMMMM
MMMMMMM:M.MMM.M.. MMMMM M..MMMMM...MMMMMMMMMMMMMMMMMM MMM
MMMM. .M..MM.M...MMMMMM..MMMMM.. MMMMMMMMMMMMMMMMMMMMMMMMMMMMMM .
MMMM..M....M.....:MMM .MMMMMM..MMMMMMM...MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMM.M.. ...M......MM.MMMMM.......MHM.M .MMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMM..MM. . MMM.....MMMMMM.M.....M ..MM..M MMMMMMMMMMMMMMMMMMM
.MMMMMHMM. ..MMMM. MMM............o..... . .MMMMMMMMMMMMMMM
MMM. M... .........................M..:.MMMMMMMMMMMM
oMMM............ .................M.M.MMMMMMMMM
.....MM........................ . MMMMMM
M.....M.....................o.MM.MMMMMMMM.
M........................M.. ...MMMMMMMMMMMMMo
:....MMM..............MMM..oMMMMMMM
M...MMM.............MMMMMMM
.............:MMMMMMMM
M..... MMM.....M
M M.............
................M
ooM.................MM MoMMMMMoooM
MMoooM......................MoooooooH..oMM
MHooooMoM.....................MMooooooM........M
oooooooMoooM......... o........MoooooooM............
Mooooooooooo.......M.........Moooooooo:..............M
MooMoooooooooM...M........:Mooooooooooo:..............M
M..oooooooooooo .........Mooooooooooooooo..............M
M...Mooo:oooooooo.M....ooooooooooooooooooo..M...........M
...oooooMoooooooM..Mooooooooooooo:oooooooM.M...........M.
M...ooooooMoo:ooooMoooooooooooooHoooooooooH:M. ...........:
M..MoooooooMoooooooooooooooooo:ooooooMooooMoM..............M
M..ooooooooooMooooooooooooooHoooooooMooHooooM...............M
...ooooooooooooooooooo:MooooooooooooooMoMoooM................
M...oooooooooooooooooooooooooooooooooooooMooMM................M
...MooooooooooooooooooooooooooooooooooooooooMo ................
...MooooooooooooooooooooooooooooooooooooooooM M................M
M...ooooooooooooooooooooooooooooooooooooooooM ................M
...MoooooooooooooooooooooooooooooooooooooooMM .:...............
.....MooooooooooooooooooooooooooooooooooooMoo .............M
M...... ooooooooooooooooooooooooooooooooooooM M..............M
M........MooooMMM MM MM MMMMMMMMMooooooooM M...............M
.........HM M: MM :MMMMMM M M...............
M..........M M MoM M M................M
M.........:M MoH M M M MooooHoooMM. M M...............M
M..........Moooo MMooM oooooMooooooooM M..............H
M.........MooooM Mooo : ooooooMooooMoooM M........ . .o.M
H.. .....ooooo oooo M MooooooooooooooM M... MMMMMMMMMMM
MMMMMMMMMMooooM M oooo . ooooooMooooooooM .MMMMMMMMMMMMMMM
MMMMMMMMMMooooH : ooooH oooooooooooooooo MMMMMMMMMMMMMMM
MMMMMMMMMMoooo ooooM Moooooooooooooooo .MMMMMMMMMMMMMMM
MMMMMMMMMMoooo ooooM MooooooooooooooooM MMMMMMMMMMMMMMM
MMMMMMMMMMoooM ooooM ooooooooooooooooo MMMMMMMMMMM:M
MMMMMMMMMMoooM MooooM oooooooooooMoooooo MH...........
. ......Mooo. MooooM oooooooooooooooooo M............M
M.M......oooo MooooM Moooooooooooooooooo: .........M.....
M.M.....Moooo MooooM ooooooooooooooooooM .M............
.......MooooH MooooM oooooooooMoooooooooo M..o...M..o....M
.o....HMooooM MooooH MooooooooMooooooooooM .:M...M.......M
M..M.....MoooM :oooo: .MooooooooHooMoooooooooM M M... ..oM.M
M...M.:.Mooo. MMMMooooo oooooooooooMoooooooooooooM ....M. M
M:M..o.Moooooooooooooo MooooooooooooooMooooooooooooM .Mo
MooooooooooooooMooooooooooooMoMoooooooooooooo
Mooooooooooooooo:ooooooooooooooooooooooooooooo
ooooooooooooooooMooooooooooMoooooooooooooooooo
ooooooooooooooooMoooooooooooMooooooooooooooooHo
ooMooooooooooooooMoooooooooooooooooooooooooooMoM
MooMoooooooooooooo.ooooooooooooooooooooooooooo:oM
MoooooooooooooooooooooooooooooooooooooooooooooooM
MoooMooooooooooooooMooooooooooooooooooooooooooooo.
MoooMooooooooooooooMoooooooooooooooooooooooooMooooM
MooooooooooooooooooMoooooooooooooooooooooooooMoooooM
MooooMoooooooooooooMoooooooooooooooooooooooooMoHooooM
ooooooMooooooooooooooooooooooooooooooooooooooooMoMoooM
MooooooooooooooooooooMooooooooooooooooooooooooooMoooooH:
MoooooooMooooooooooooMoooooooooooooooooooooooooooooHoooM
MooooooooMoooooooooooMoooooooooooooooooooooooooMoooMooooM
Moooooooooooooooooooooooooooooooooooooooooooooo.oooMooooo
MoooooooooooooooooooooooooooooooooooooooooooooMoooooooooM
MooooooooooooooooooooMoooooooooooooooooooooooooooooooooM
MooooooooooooooooooooMHooooooooooooooooooooMoooo:ooooo
MMooooooooooooooooooMoMHoooooooooooooooooooooooMooooo
MMoooooooooooooooMMooo MMooooooooooooooooooooooooooM
MMMoooooooooooooMooooo oooooooooooooooooooooMooooo
MooMMoooooooooMoooMMoM ooooHooooooooooooooooMooooM
MooooMooooooMooooMoooM MoooooMoooooooooooooMooooo
ooooooMMooooooooMooooM MoooooooooMooooooooooooooM
HooooooMoooooooMooooM HoooooooHooMooooooooooooo
oooMoooooooooHoooM MoooooooooMoooooooooM
HooooooooooooHM MooooooooMMoooooooM
MMMMMMMMMMMMMM Moooooo:MooooHMM
MMMMMMM: ... MMMMMMMMMMMMMM
M............M MMMMMMMMM ....
M.MM.......... M.............M
M ..............MM M..............
MMMMM............MMMM ..MMMMMMMM ....M
MMMMMMMMMMMMMMMMMMMMMMMM MMMMMMMMMMMMM...M
.MMMMMMMMMMMMMMMMMMMMMMMMMM MMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMM MMMMMMMMMMMMMMMMMMM
:MMMMMMMMMMMMMMMMMMH MMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMM
HMMMMMM
*/
#include <bits/stdc++.h>
using namespace std;
#define fo(i, n) for (ll i = 0; i < n; i++)
#define Fo(i, k, n) for (ll i = k; k < n ? i < n : i > n; k < n ? i += 1 : i -= 1)
#define ll long long
#define pb push_back
#define F first
#define S second
typedef vector<long long> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
// const ll MOD = 1e9 + 7;
#define yes cout<<"YES\n";
#define no cout<<"NO\n";
//Segment Trees Code
// int n, t[4*n];
// void build(int a[], int v, int tl, int tr) {
// if (tl == tr) {
// t[v] = a[tl];
// } else {
// int tm = (tl + tr) / 2;
// build(a, v*2, tl, tm);
// build(a, v*2+1, tm+1, tr);
// t[v] = t[v*2] + t[v*2+1];
// }
// }
// int sum(int v, int tl, int tr, int l, int r) {
// if (l > r)
// return 0;
// if (l == tl && r == tr) {
// return t[v];
// }
// int tm = (tl + tr) / 2;
// return sum(v*2, tl, tm, l, min(r, tm))
// + sum(v*2+1, tm+1, tr, max(l, tm+1), r);
// }
// void update(int v, int tl, int tr, int pos, int new_val) {
// if (tl == tr) {
// t[v] = new_val;
// } else {
// int tm = (tl + tr) / 2;
// if (pos <= tm)
// update(v*2, tl, tm, pos, new_val);
// else
// update(v*2+1, tm+1, tr, pos, new_val);
// t[v] = t[v*2] + t[v*2+1];
// }
// }
// Segment Trees Code End
// DSU Code
ll find(vll &father,ll node){
if(father[node]!=node){
father[node] = find(father,father[node]);
}
return father[node];
}
void merge(vll &father,ll a,ll b,vll &size){
ll r1 = find(father,a);
ll r2 = find(father,b);
if(r1!=r2){
if(size[r1]>size[r2]){
father[r2] = r1;
size[r1] = max(size[r1],size[r2]+1);
}
else{
father[r1] = r2;
size[r2] = max(size[r2],size[r1]+1);
}
}
}
// DSU Code End
int query(ll k, vector<ll>& path){
cout << "? " << k << endl;
cout.flush();
ll x; cin >> x;
if(x == -1) exit(0);
path.resize(x);
for(int i = 0; i < x; i++) cin >> path[i];
return x;
}
vector<vll> adj;
vll vis;
vll vis1;
ll root;
ll dfs(ll u, ll p) {
if(u != root && vis[u] >= vis1[u]){
return 1;
}
if(u != root && adj[u].size() == 1){
return 1;
}
ll friends = 0;
for(auto x: adj[u]){
if(x != p){
friends += dfs(x, u);
}
}
return friends;
}
vll get_primes(ll limit) {
vector<bool> is_prime(limit + 1, true);
is_prime[0] = is_prime[1] = false; // 0 and 1 are not primes
for (ll p = 2; p * p <= limit; p++) {
// If is_prime[p] is not changed, then it is a prime
if (is_prime[p]) {
// Update all multiples of p starting from p^2
for (ll i = p * p; i <= limit; i += p) {
is_prime[i] = false;
}
}
}
vll primes;
for (ll p = 2; p <= limit; p++) {
if (is_prime[p]) {
primes.pb(p);
}
}
return primes;
}
const int MAX = 200005;
int d[MAX];
const int MOD = 676767677;
void precompute() {
for (int i = 1; i < MAX; i++) {
for (int j = i; j < MAX; j += i) {
d[j]++;
}
}
}
ll power(ll base, ll exp) {
ll res = 1;
base %= MOD;
while (exp > 0) {
if (exp % 2 == 1) res = (res * base) % MOD;
base = (base * base) % MOD;
exp /= 2;
}
return res;
}
ll modInverse(ll n) {
return power(n, MOD - 2);
}
ll nCr(ll n, ll r) {
if (r < 0 || r > n) return 0;
if (r > n - r) r = n - r;
ll num = 1, den = 1;
for (ll i = 0; i < r; i++) {
num = (num * (n - i)) % MOD;
den = (den * (i + 1)) % MOD;
}
return (num * modInverse(den)) % MOD;
}
map<ll,ll> dp;
ll get_depth(ll n) {
if (n == 0) return 0;
if (n == 1) return 1;
if (dp.count(n)) return dp[n];
ll left = (n - 1) / 2;
ll right = n - 1 - left;
return dp[n] = (get_depth(left) + get_depth(right) + n) % MOD;
}
void solve(){
// freopen("atlarge.in","r",stdin);
// freopen("atlarge.out","w",stdout);
ll n,s;cin>>n>>s;
queue<pair<ll,ll>> q;
char arr[n][n];
pair<ll,ll> p1,p2;
vector<vll> vis(n,vll(n,-1));
fo(i,n){
fo(j,n){
cin>>arr[i][j];
if(arr[i][j]=='M'){p1 = {i,j};}
if(arr[i][j]=='D'){p2 = {i,j};}
if(arr[i][j]=='H'){q.push({i,j});vis[i][j]=0;}
}
}
ll dx[4] = {1,-1,0,0};
ll dy[4] = {0,0,1,-1};
while(!q.empty()){
auto k = q.front();
q.pop();
fo(i,4){
ll x = k.F+dx[i];
ll y = k.S+dy[i];
if(x>=0 && x<n && y>=0 && y<n && (arr[x][y]=='G'||arr[x][y]=='M') && vis[x][y]==-1){
q.push({x,y});
vis[x][y] = vis[k.F][k.S]+1;
}
}
}
ll ans = -1;
ll r = 0;
ll e = n*n;
vector<vll> vis1(n,vll(n,-1));
while(r<=e){
ll mid = (r+e)/2;
queue<pair<pair<ll,ll>,ll>> q1;
vis1[p1.F][p1.S] = 0;
q1.push({p1, 0});
while(!q1.empty()){
auto k = q1.front();
q1.pop();
ll time = mid + (k.S+1)/s;
fo(i,4){
ll x = k.F.F+dx[i];
ll y = k.F.S+dy[i];
if(x>=0 && x<n && y>=0 && y<n && (arr[x][y]=='G'||arr[x][y]=='D') && vis1[x][y]==-1 && (vis[x][y] == -1 || vis[x][y]>time)){
q1.push({{x,y},k.S+1});
vis1[x][y] = time;
}
}
}
if(vis1[p2.F][p2.S]!=-1){ans = mid;r = mid + 1;}
else{e = mid - 1;}
fo(i,n){
fo(j,n){vis1[i][j]=-1;}
}
}
cout<<ans;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll t;
t = 1;
precompute();
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
