Little Bear and the Honey Pot

A little bear finds a secret honey pot that the bees have hidden in the forest. Just as it starts to eat the honey, a nearby bee spots it and signals the rest of the swarm. Sensing that countless bees will soon leave their hives to attack, the bear decides to flee home while avoiding them. The bear wants to stay at the honey pot eating for as long as possible, then leave and reach home safely. Compute the longest time the bear can keep eating honey.

The forest is an $N \times N$ grid. Every cell is a tree, grass, a hive, or the bear's home. The bear moves only to a cell orthogonally adjacent (no diagonal moves), can never enter a tree or hive cell, and may only step onto grass cells. The bear can move at most $S$ cells per minute.

At the moment the first bee signals, the bear is on the grass cell that holds the honey pot. Every hive cell contains infinitely many bees (there may be more than one hive cell). The forest clock advances one minute at a time, and each minute the following events happen in order.

1. If the bear is eating, it decides whether to keep eating or to leave. If it keeps eating, it cannot move during that minute. If it leaves, it departs at once and moves up to $S$ cells during that minute. Once it leaves the pot it can never eat again.
2. After the bear has eaten or moved for one minute, the instant that minute ends the bees spread: from every cell they occupy, the bees simultaneously advance one step into every orthogonally adjacent grass cell. Once bees occupy a cell they remain there forever, so the set of bee-occupied cells only grows over time.

To restate the spread: at the instant of the signal, only hive cells hold bees. When the first minute ends, the bees occupy the hive cells and every grass cell adjacent to them. When the second minute ends, they also occupy the grass cells adjacent to those, and so on; after enough time the bees occupy every grass cell reachable from a hive.

Neither the bear nor the bees can leave the forest, and the bees can never enter the bear's home cell. The time the bear spends eating is an integer number of minutes. If at any instant the bear shares a cell with the bees, it is caught.

Given the map of the forest, write a program that computes the longest time the bear can stay at the honey pot eating while still being able to reach home without being caught.

Read the following data from standard input.

• The first line contains two integers $N$ and $S$, separated by a space.
• Each of the next $N$ lines contains $N$ characters with no spaces, describing the map. The characters mean:
  • T: a tree cell
  • G: a grass cell
  • M: the bear's starting cell (the honey pot); it is also a grass cell.
  • D: the bear's home. The bear may enter it, but the bees may not.
  • H: a hive cell

The map contains exactly one M, exactly one D, and at least one H. There is at least one grass (G) path connecting the bear's starting cell to its home, and at least one grass path connecting some hive to the honey pot (the bear's starting cell). The bear's home or a hive may be adjacent to the bear's starting cell.

• $1 \le N \le 800$
• $1 \le S \le 1{,}000$

Print a single integer on one line to standard output: the longest time in minutes that the bear can keep eating honey while still reaching home safely from its starting cell.

If it is impossible for the bear to reach home without being caught, print $-1$.

In the first example, the bear eats for one minute and then follows the straight shortest path to the right, reaching home safely over the next two minutes. Hence the longest time it can eat is one minute, and the answer is 1.