/*
 * Solution by Christian Kauth - July 2010 - Solves all test cases at
 * http://www.ioi2009.org/downloads/ioi2009_tests.zip
 * Imagine you were told how long Mecho can continue eating honey and 
 * you are then asked whether Mecho can still make it home. You can answer
 * this easy question by simulating the bees' and the bear's spread through
 * the grid using Breadth-First-Search. Observe that the bees' spread is 
 * independent from Mecho's eating time (so do not recompute it)! Now you can 
 * repeatedly simulate Mecho's escape for different eating times and find the 
 * maximum eating time by binary search. [Remember this powerful technique!
 * Linear search will break down for most of the test cases]
 */

#include <iostream>
#include <queue>
using namespace std;

#define MAX_SIZE 802			// Maximum size of the grid (800+2 for boundaries)
#define OUT '?'					// this defines 'outside the grid'
#define INF 1000000000			// a finite value for infinity ;)

const int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};	// moving directions

int N, S;
char grid[MAX_SIZE][MAX_SIZE];				// the grid (tree, grass, hive, honey or home)
long long beeTime[MAX_SIZE][MAX_SIZE];		// the time it takes the bees to reach locations inside the grid
long long mechoTime[MAX_SIZE][MAX_SIZE];	// the time it takes Mecho to reach locations inside the grid

/*
 * Read the test case and set boundaries to the grid
 */
void read_case()
{
	int i, j;

	cin>>N>>S;
	for (i=1; i<=N; i++)
		for (j=1; j<=N; j++)
			cin>>grid[i][j];

	for (i=0; i<=N+1; i++)
		grid[0][i] = grid[i][0] = grid[N+1][i] = grid[i][N+1] = OUT;
}

/*
 * Compute the time it takes the bees to reach each accessible location
 * Breadth-First-Search (BFS)
 */
void compute_beeTime()
{
	queue<int> Q;
	int i, j, ii, jj;

	// add hives to queue
	for (int i=1; i<=N; i++)
		for (int j=1; j<=N; j++)
			if (grid[i][j]=='H')
			{
				Q.push(i*(N+2)+j);
				beeTime[i][j] = 0;
			}
			else
				beeTime[i][j] = INF;

	// BFS
	while (!Q.empty())
	{
		i = (Q.front())/(N+2);
		j = (Q.front())%(N+2);
		Q.pop();
		for (int d=0; d<4; d++)
		{
			ii = i+dir[d][0];
			jj = j+dir[d][1];
			if (grid[ii][jj]=='G' || grid[ii][jj]=='M')
				if (beeTime[ii][jj] == INF)
				{
					beeTime[ii][jj] = beeTime[i][j]+S;
					Q.push(ii*(N+2)+jj);
				}
		}
	}
}

/*
 * Uses BFS to see whether there is a path from the honey pot to Mecho's home such that
 * mecho isn't caught by the bees when eating honey for another 'eatTime' minutes
 */
bool mecho_gohome(int eatTime)
{
	queue<int> Q;
	int i, j, ii, jj;

	// add honey pot to queue
	for (int i=1; i<=N; i++)
		for (int j=1; j<=N; j++)
			if (grid[i][j]=='M' && eatTime*S < beeTime[i][j])
			{
				Q.push(i*(N+2)+j);
				mechoTime[i][j] = eatTime*S;
			}
			else
				mechoTime[i][j] = INF;

	// BFS
	while (!Q.empty())
	{
		i = (Q.front())/(N+2);
		j = (Q.front())%(N+2);
		if (grid[i][j]=='D')
			return true;
		Q.pop();
		for (int d=0; d<4; d++)
		{
			ii = i+dir[d][0];
			jj = j+dir[d][1];
			if (grid[ii][jj]=='G' || grid[ii][jj]=='D')
				if (mechoTime[ii][jj]==INF && mechoTime[i][j]+1<beeTime[ii][jj])
				{
					mechoTime[ii][jj] = mechoTime[i][j]+1;
					Q.push(ii*(N+2)+jj);
				}
		}
	}
	return false;
}

/*
 * The few lines you should always think of ;)
 */
long long binary_search()
{
	long long l(-1), r(N*N), x;

	do
	{
		x = (l+r+1)/2;
		mecho_gohome(x) ? l=x : r=x-1;
	} while (r > l);

	return r;
}

int main()
{
	read_case();
	compute_beeTime();
	cout<<binary_search()<<endl;
	return 0;
}