Mecho’s Honey Escape

Mecho the bear has discovered a treasure trove—a secret honey pot full of honey! He happily devours his discovery until a bee spots him and sounds an alarm. At that moment, swarms of bees will begin spreading out from their hives in the forest to capture him. Although the honey is delicious, Mecho must leave as late as possible and still get safely home.

The forest is represented as an N×N grid. Each cell of the grid is one of the following:

• Grass cell (represented by a '.' or 'M') – open land on which Mecho may walk and in which the honey pot is located at Mecho’s starting cell (denoted by 'M').
• Beehive cell (represented by 'H') – initially occupied by bees.
• Tree cell (represented by 'T') – an obstacle that Mecho cannot pass through.
• Home cell (represented by 'D') – Mecho’s destination. Note that bees do not enter this cell.

Two cells are adjacent if they share a side (north, south, east, or west). Mecho can only move on grass cells (or enter his home) and cannot step onto tree or beehive cells. Being a clumsy bear, every time he moves he can only step into one of the adjacent cells; however, when he leaves the honey pot he can make up to S steps per minute (i.e. he can travel along a contiguous path of up to S moves in one minute). Once he leaves the honey pot, he cannot eat honey again.

The events unfold in discrete minutes. When the bee alarm sounds (time 0), Mecho is in his starting cell (the honey‐laden grass cell marked ‘M’), and the bees are in every cell that contains a beehive (‘H’). In each subsequent minute the following occurs in order:

1. If Mecho is still eating honey, he chooses either to continue eating (and remain in place for the full minute) or to leave immediately and use that minute to move up to S steps. (Note that if he starts moving, he cannot eat honey in a later minute.)
2. After Mecho’s action (eating or moving) is completed, the bees spread one unit. In particular, the bees spread from any cell that currently has bees to every adjacent grass cell (cells originally marked with '.' or 'M'). Once bees occupy a cell, they remain there permanently. (Bees never enter tree cells, home cells, or any cell that is not grass.)

If at any time Mecho finds himself in a cell that is occupied by bees, he is caught.

Task: Given the forest grid, determine the maximum number of whole minutes that Mecho can continue eating honey at his starting position while still being able to reach his home safely before the bees catch him.

Notes on movement and safety:

• If Mecho chooses to wait for t minutes initially, the bees will have spread t times before he makes his first move. In order for his starting cell to be safe at time t, the bees must not have reached it by then.
• When moving, Mecho can traverse up to S steps in one minute along a contiguous path through walkable cells (grass cells and/or the home cell). During his move, he is not checked by the bees. However, at the end of the minute, if his landing cell (unless it is his home) is already occupied by bees (or the bees arrive at exactly that minute), he will be caught.
• Intermediate cells that Mecho passes through in a minute are not checked for bees, but they must be physically traversable (i.e. not tree or beehive cells) and must not already be occupied by bees at the start of the minute.

You are to write a program that, given the map along with the maximum step count S per minute, computes the maximum delay (in full minutes) Mecho can enjoy his honey while still being able to reach his home safely.

inputFormat

The first line contains two integers N and S where N (2 ≤ N ≤ 1000) is the size of the grid and S (1 ≤ S ≤ 10) is the maximum number of steps Mecho can take in one minute.

The following N lines each contain a string of length N consisting only of the characters:

• 'M' — Mecho’s starting cell (a grass cell with the honey pot). There is exactly one 'M'.
• 'D' — Mecho’s home. There is exactly one 'D'.
• '.' — A grass cell.
• 'T' — A tree cell (impassable).
• 'H' — A beehive cell (initially occupied by bees).

Note: Bees spread only into grass cells (i.e. cells originally containing '.' or 'M').

outputFormat

Output a single integer — the maximum number of whole minutes that Mecho can continue eating honey and still reach his home safely. If it is impossible for Mecho to reach home under any circumstances, output -1.

sample

3 1
M.H
...
..D

1