Khu rừng của Mecho có dạng lưới ô vuông N x N đơn vị, có các cạnh chạy song song theo hướng bắc – nam và đông – tây. Ở mỗi ô của lưới là cây hoặc cỏ hay là hang của Mecho. Mecho là một chú gấu vụng về, nên mỗi lần chú nhảy một bước, chú chỉ nhảy được theo một trong các hướng bắc, nam, đông hoặc tây và mỗi bước nhảy có độ dài đúng một đơn vì. Mecho chỉ chạy được vào các ô cỏ, không nhảy vào ô có cây và chú có thể thực hiện tối đa S bước trong một phút.

Khi tín hiệu báo động của đàn ong vang lên, Mecho đang ở ô có bầu mật và tất cả ông đang ở những ô có tổ ong (trong rừng có thể có nhiều hơn một tổ ong). Từ lúc này trờ đi, cứ mỗi phúc sẽ xảy ra một sự kiện theo trình tự sau:

Nếu Mecho còn ở chỗ bầu mật, chú có thể ở lại tiếp tục ăn hay rời đi. Nếu chú tiếp tục ăn thì suốt cả phút đó chú không rời đi đâu. Trong trường hợp ngược lại, nếu bỏ chạy, chú sẽ thực hiện tối đa S bước nhảy trong rừng theo cách đã mô tả ở trên. Mecho không mang theo được một giọt mật nào, vì vậy nếu đã chạy, chú không awnt hêm được chút mật nào.

Sau khi Mecho quyết định ở lại ăn hay bỏ chạy trong nguyên một phút, ong sẽ tràn ra thêm một đơn vị trong lưới, Ong chỉ tràn đến các ô cỏ. Đặc biệt lưu ý là, đàn ong tràn sang mọi ô cỏ khác kề cạnh(theo hướng đông, tây, nam, bắc chứ không theo đường chéo) từ những ô đang có ong. Như vậy, một ô đã có ong thì từ đó trở đi luôn luôn có ong(tóm lại đàn ông không di chuyển mà là phát triển).

Nói cách khác, đàn ong tỏa ra theo cách sau: khi ong nghe thấy tín hiệu báo động chúng chỉ ở tại ô có tổ ong. Đến cuối phút đầu tiên chúng sẽ tỏa ra các ô cỏ kề cạnh (và vẫn còn ong trên các ô có tổ). Cuối phút thứ hai, đàn ong tỏa rộng ra các ô cỏ kề cạnh với những ô có ong trước đó và mọi thứ cứ thể tiếp diễn. Nếu thời gian đủ lâu, ong sẽ tỏa ra chiếm tất cả các ô cỏ của rừng mà chúng có thể lan đến.

Cả Mecho lẫn đàn ong đều không ra khỏi khu rừng. Ta cũng thấy rằng, theo quy tắc trên, chú gấu Mecho luôn luôn ăn mật ong trong một khoảng nguyên lần phút.

BÀI TOÁN

Cho bản đồ của khu rừng, hãy viết chương trình xác định tối đa số phút Mecho có thể ăn mật ở vị trí ban đầu của mình, trong khi chú vẫn có thể chạy về hang an toàn mà không bị một con ong nào đuổi kịp.

GIỚI HẠN

1 ≤ N ≤ 800 Kích thước (độ rộng) khu rừng.

1 ≤ S ≤1000 Số bước tối đa Mecho có thể thực hiện trong một phút.

INPUT

Chương trình của bạn phải đọc từ standard input các dữ liệu sau:

Dòng đầu tiên chứa các số nguyên N và S, cách nhau một dấu cách.

N dòng tiếp theo biểu diễn bản đồ khu rừng. Mỗi dòng trong số các dòng này chứa N kí tự, mỗi kí tự mô tả một ô của lưới. Có thể có các kí tự với ý nghĩa như sau:

T Ô có cây.

G Ô cỏ.

M Vị trí ban đầu của Mecho và là ô cỏ.

D Hang của Mecho. Mecho vào được, nhưng ong thì không thể bay vào.

H Ô có tổ ông, các tổ ong đều ở trên cây.

LƯU Ý: Đảm bảo là trên bản đồ chỉ có đúng một kí tự M, đúng một kí tự D và có ít nhất một kí tự H. Đảm bảo có dãy kí tự G kề nhau nối với Mecho tới hang của chú, cũng như có dãy kí tự G kề nhau nối ít nhất một tổ ong với ô có bầu mật (tức là vị trí ban đầu của Mecho). Các dãy này có thể có độ dài bằng 0, khi hang của Mecho hoặc tổ ong nằm kề với vị trí ban đầu của Mecho. Ngoài ra, cần lưu ý là ong không thể vượt qua hoặc bay ngang ô có hang của Mecho. Như vậy, đối với ong, hang của Mecho cũng giống như cây.

OUTPUT

Chương trình của bạn phải ghi ra standard output một dòng chứa một số nguyên: số phút tối đa Mecho có thể ăn mật ở chỗ có bầu mật và vẫn chạy thoát an toàn về hang.

Nếu cho Mecho không có cách nào chạy thoát về hang mà không bị ong đốt thì số nguyên mà bạn phải đưa ra standard output là -1.

CÁCH CHẤM ĐIỂM

Sẽ có một nhóm test với tổng số điểm là 40, trong đó N không vượt quá 60.

VÍ DỤ

Sau khi ăn mật trong một phút, Mecho theo con đường ngắn nhất chạy thẳng sang phải về hang của mình sau 2 phút nữa, tránh ong đốt.

Sau khi ăn mật trong 2 phút, Mecho thực hiện các bước chạy →↑→ trong phút thứ 3, sau đó là các bước →→→ trong phút thứ tư và các bước chạy ↓→ trong phút thứ năm.

School@net