#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pair<int, int>> vpi;
#define x first
#define fastio() \
ios::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0)
#define y second
#define PB push_back
#define MP make_pair
#define REP(i, a, b) for (int i = a; i < b; i++)
int mod = 1e9 + 7;
int mod_inverse_2 = 500000004; // Modular inverse of 2 modulo (10^9 + 7), also
// the number has to be in long long otherwise
// if the number is int need to mutiply by 1LL
const int N = 100009;
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};
ll bound = 1e18;
vector<vector<char>> grid;
ll n, s;
pair<ll, ll> bear, home;
vector<pair<ll, ll>> hives;
vector<vector<ll>> beesDepths;
vector<vector<ll>> bearDepths;
bool valid = false;
void floodfill(ll i, ll j, vector<vector<bool>> &visited, ll mins)
{
REP(k, 0, 4)
{
if (i + dy[k] < 1 || j + dx[k] < 1 || i + dy[k] > n || j + dx[k] > n)
{
continue;
}
if (visited[i + dy[k]][j + dx[k]])
{
continue;
}
if ((bearDepths[i + dy[k]][j + dx[k]] + 1) / s >=
beesDepths[i + dy[k]][j + dx[k]] - mins)
{
continue;
}
if (grid[i + dy[k]][j + dx[k]] == 'D')
{
valid = true;
return;
}
if (grid[i + dy[k]][j + dx[k]] != 'G')
{
continue;
}
visited[i][j] = true;
floodfill(i + dy[k], j + dx[k], visited, mins);
}
}
void solve()
{
cin >> n >> s;
grid.resize(n + 1);
beesDepths.resize(n + 1);
REP(i, 0, n + 1)
{
grid[i].resize(n + 1);
beesDepths[i].resize(n + 1, 1e18);
}
REP(i, 1, n + 1)
{
REP(j, 1, n + 1)
{
cin >> grid[i][j];
if (grid[i][j] == 'M')
{
bear = {i, j};
}
if (grid[i][j] == 'D')
{
home = {i, j};
}
if (grid[i][j] == 'H')
{
hives.PB({i, j});
}
}
}
deque<pair<pair<ll, ll>, ll>> q;
REP(i, 0, hives.size())
{
q.PB(MP(hives[i], 0));
beesDepths[hives[i].x][hives[i].y] = 0;
}
while (!q.empty())
{
pair<pair<ll, ll>, ll> cur = q.front();
pair<ll, ll> coords = cur.x;
ll d = cur.y;
q.pop_front();
REP(k, 0, 4)
{
if (coords.x + dy[k] < 1 || coords.y + dx[k] < 1 ||
coords.x + dy[k] > n || coords.y + dy[k] > n ||
grid[coords.x + dy[k]][coords.y + dx[k]] != 'G')
{
continue;
}
if (beesDepths[coords.x + dy[k]][coords.y + dx[k]] > d + 1)
{
beesDepths[coords.x + dy[k]][coords.y + dx[k]] = d + 1;
q.PB(MP(MP(coords.x + dy[k], coords.y + dx[k]), d + 1));
}
}
}
ll l = 0;
ll r = n * n;
q.PB(MP(bear, 0));
bearDepths.resize(n + 1);
REP(i, 0, n + 1) { bearDepths[i].resize(n + 1, 1e18); }
bearDepths[bear.x][bear.y] = 0;
while (!q.empty())
{
pair<pair<ll, ll>, ll> cur = q.front();
q.pop_front();
pair<ll, ll> coords = cur.x;
ll d = cur.y;
REP(k, 0, 4)
{
if (coords.x + dy[k] < 1 || coords.y + dx[k] < 1 ||
coords.x + dy[k] > n || coords.y + dy[k] > n ||
grid[coords.x + dy[k]][coords.y + dx[k]] != 'G')
{
continue;
}
if (bearDepths[coords.x + dy[k]][coords.y + dx[k]] > d + 1)
{
bearDepths[coords.x + dy[k]][coords.y + dx[k]] = d + 1;
q.PB(MP(MP(coords.x + dy[k], coords.y + dx[k]), d + 1));
}
}
}
while (l <= r)
{
ll mid = l + (r - l) / 2;
vector<vector<bool>> bearVis(n + 1);
valid = false;
REP(i, 0, n + 1) { bearVis[i].resize(n + 1, false); }
bearVis[bear.x][bear.y] = true;
floodfill(bear.x, bear.y, bearVis, mid);
if (valid)
{
l = mid + 1;
}
else
{
r = mid - 1;
}
cout << l << " " << r << "\n";
}
cout << l - 1 << "\n";
}
int main()
{
fastio();
solve();
return 0;
}
