\includegraphics{https://static.e-olymp.com/content/16/166632343fa587e3d0b8922616b00294ff837350.gif} Ведмідь Міша знайшов маленький скарб - захований горщик меду! Він із задоволенням поїдав мед, але раптом одна бджола його помітила та забила тривогу. Міша знає, що після цього бджоли вилетять зі своїх вуликів і будуть розлітатися навколо, щоб наздогнати його. Він знає, що потрібно кидати горщик і швидко йти додому, але мед такий солодкий, що Міша не хоче кидати його їсти занадто рано. Допоможіть Міші визначити останній можливий момент, коли він може припинити їсти мед. Ліс представлений картою у вигляді квадратної сітки, яка складається з \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}.