\includegraphics{https://static.e-olymp.com/content/16/166632343fa587e3d0b8922616b00294ff837350.gif} Медведь Миша нашел маленькое сокровище -- спрятанный горшочек меда! Он c удовольствием поедал мед, но вдруг одна пчела его заметила и забила тревогу. Миша знает, что после этого пчелы вылетят из своих ульев и будут разлетаться вокруг, чтобы настичь его. Он знает, что нужно бросать горшочек и быстро идти домой, но мед так сладок, что Миша не хочет бросать его есть слишком рано. Помогите Мише определить последний возможный момент, когда он может прекратить есть мед. Лес представлен картой в виде квадратной сетки, которая состоит из \textbf{n}×\textbf{n} единичных ячеек, стороны которых параллельны направлениям <<север-юг>> и <<запад-восток>>. Каждая ячейка леса занята либо деревом, либо травой, либо ульем, либо Мишиным домом. Две ячейки называются смежными, если одна из них находится непосредственно к северу, югу, востоку или западу от другой, но не по диагонали. Миша неповоротлив, поэтому он может перемещаться только в смежную ячейку. Миша может перемещаться только по ячейкам с травой и не может перемещаться по ячейкам с деревьями или ульями. Также он не может перемещаться больше, чем на \textbf{s} ячеек в минуту. В момент, когда прозвучала тревога, Миша находится в ячейке с травой, где он нашел горшочек с медом, а все пчелы -- в ячейках, где расположены ульи (в лесу может быть больше одного улья). С этого момента, на протяжении каждой следующей минуты происходят следующие события в таком порядке: \begin{itemize} \item Если Миша все еще ест мед, он решает, будет ли он продолжать есть или будет уходить. Если он продолжает есть мед -- он не перемещается всю минуту. Иначе, он немедленно уходит и перемещается по лесу не более чем на \textbf{s} ячеек, как описано выше. Миша не может брать с собой мед, и как только он ушел, он уже не может его есть. \item Как только Миша заканчивает есть или перемещаться в течение минуты, пчелы разлетаются на одну ячейку дальше, занимая только ячейки с травой. Точнее, пчелы разлетаются во все ячейки с травой, смежные с любой ячейкой, где уже есть пчелы. Как только в ячейке появляются пчелы, они там остаются навсегда (пчёлы не перемещаются, а распространяются). \end{itemize} Другими словами, пчелы разлетаются так: когда звучит тревога, пчелы находятся в ячейках, где расположены ульи. В конце первой минуты они занимают все ячейки с травой, смежные с ульями, и остаются в тех ячейках, где расположены ульи. В конце второй минуты пчелы дополнительно занимают все ячейки с травой, смежные со смежными с ульями ячейками, и так далее. Имея достаточно времени, пчелы займут все ячейки с травой, которые они могут достичь. Ни Миша, ни пчелы не могут покидать пределы леса. Также обратите внимание, что согласно описанным правилам, Миша ест мед целое число минут. Пчелы настигают Мишу, если в какой-то момент времени Миша оказывается в ячейке, занятой пчелами. Напишите программу, которая по карте леса определяет наибольшее количество минут, на протяжении которых Миша может продолжать есть мед в своем исходном расположении, все еще имея возможность попасть домой до того, как пчелы его настигнут. \InputFile Первая строка содержит два целых числа - размер (длина стороны) карты леса \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{800}) и максимальное количество перемещений \textbf{s} (\textbf{1} ≤ \textbf{s} ≤ \textbf{1,000}), которые может делать Миша в каждую минуту, разделенные пробелом. Последующие \textbf{n} строк задают карту леса. Каждая из этих строк содержит \textbf{n} символов, каждый символ задает одну ячейку на сетке. Возможные символы и их значения описаны ниже: \textbf{T} обозначает ячейку с деревом \textbf{G} обозначает ячейку с травой\textbf{M} обозначает начальное расположение Миши и горшочка меда в ячейке с травой\textbf{D} обозначает ячейку где расположен Мишин дом, в который Миша может попасть, а пчелы не могут\textbf{H} обозначает ячейку с ульем \textbf{ПРИМЕЧАНИЕ}: Гарантируется, что карта леса содержит ровно одну букву \textbf{M}, ровно одну букву \textbf{D} и, по крайней мере, одну букву \textbf{H}. Также гарантируется, что существует последовательность смежных ячеек \textbf{G}, которые соединяют ячейку с начальным расположением Миши и ячейку, где расположен Мишин дом, так же как и последовательность смежных ячеек \textbf{G}, которые соединяют хотя бы одну из ячеек с ульем с ячейкой с горшочком (то есть, с ячейкой с Мишиным начальным расположением). Последовательности могут быть и с длиной, равной нулю, в случае, если ячейка с Мишиным домом или ячейка с ульем являются смежными с ячейкой с начальным расположением Миши. Также заметьте, что пчелы не могут распространяться через ячейку с Мишиным домом. Для пчел она -- как ячейка с деревом. \OutputFile Одно целое число - максимально возможное количество минут, на протяжении которых Миша может продолжать есть мед в начальном расположении, имея возможность безопасно вернуться домой. Если Миша не имеет возможность вернуться домой до того, как пчелы его настигнут, ваша программа должны выводить отрицательное число \textbf{-1}.