Chú gấu Mecho vừa tìm thấy một kho báu nhỏ: hũ mật bí mật của bầy ong, chứa đầy mật! Mecho đang vui vẻ thưởng thức thì bất ngờ bị một con ong phát hiện và báo động. Mecho biết rằng ngay lúc này, những đàn ong sẽ xuất hiện từ các tổ và bắt đầu lan khắp nơi để tìm bắt mình. Mecho phải rời hũ mật và nhanh chóng về nhà, nhưng mật quá ngọt nên chú không muốn rời đi quá sớm. Hãy giúp Mecho xác định thời điểm muộn nhất mà chú có thể rời đi.

Khu rừng của Mecho được biểu diễn bằng một lưới vuông gồm \(N \times N\) ô đơn vị, có các cạnh song song với các hướng bắc - nam và đông - tây. Mỗi ô chứa một cái cây, một bãi cỏ, một tổ ong hoặc nhà của Mecho. Hai ô được xem là kề nhau nếu một ô nằm ngay phía bắc, nam, đông hoặc tây của ô kia; các ô chỉ tiếp xúc theo đường chéo không kề nhau. Mecho khá vụng về nên mỗi bước phải đi sang một ô kề. Mecho chỉ có thể đi trên cỏ, không thể đi xuyên qua cây hoặc tổ ong, và có thể đi tối đa \(S\) bước mỗi phút.

Tại thời điểm báo động vang lên, Mecho đang ở ô cỏ chứa hũ mật, còn ong đang ở tất cả các ô chứa tổ ong; trong rừng có thể có nhiều tổ. Trong mỗi phút kể từ thời điểm này, các sự kiện diễn ra theo đúng thứ tự sau:

1. Nếu Mecho vẫn đang ăn mật, chú quyết định tiếp tục ăn hay rời đi. Nếu tiếp tục ăn, chú không di chuyển trong cả phút đó. Nếu rời đi, chú lập tức di chuyển tối đa \(S\) bước trong rừng theo quy tắc trên. Mecho không thể mang mật theo, nên một khi đã di chuyển, chú không thể ăn mật nữa.
2. Sau khi Mecho đã ăn hoặc di chuyển xong trong cả phút đó, ong lan thêm một ô trên lưới và chỉ lan vào các ô cỏ. Cụ thể, ong lan vào mọi ô cỏ kề với bất kỳ ô nào đã có ong. Khi một ô đã có ong, ô đó sẽ luôn có ong về sau; nghĩa là vùng có ong lớn dần chứ không chuyển từ nơi này sang nơi khác.

Nói cách khác, khi báo động vang lên, ong chỉ chiếm các ô có tổ. Cuối phút thứ nhất, ong chiếm tất cả các ô cỏ kề với tổ ong, đồng thời vẫn ở trong các tổ. Cuối phút thứ hai, ong chiếm thêm mọi ô cỏ kề với các ô cỏ kề tổ ong, và cứ thế tiếp tục. Sau đủ thời gian, ong sẽ đồng thời chiếm tất cả các ô cỏ trong rừng mà chúng có thể tới được.

Cả Mecho lẫn ong đều không thể ra ngoài khu rừng. Theo các quy tắc trên, thời gian Mecho ăn mật luôn là một số nguyên phút. Mecho bị bắt nếu tại bất kỳ thời điểm nào chú ở trong một ô có ong.

Cho bản đồ khu rừng, hãy viết chương trình xác định số phút lớn nhất mà Mecho có thể tiếp tục ăn mật tại vị trí ban đầu nhưng vẫn về tới nhà trước khi bị ong bắt.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa hai số nguyên \(N\) và \(S\), cách nhau bởi một dấu cách.
• \(N\) dòng tiếp theo mô tả bản đồ khu rừng. Mỗi dòng chứa \(N\) ký tự, mỗi ký tự biểu diễn một ô đơn vị của lưới.

Các ký tự có ý nghĩa như sau:

Bản đồ được bảo đảm có đúng một ký tự M, đúng một ký tự D và ít nhất một ký tự H. Ngoài ra, tồn tại một dãy các ô G liên tiếp kề nhau nối Mecho với nhà, và một dãy các ô G liên tiếp kề nhau nối ít nhất một tổ ong với hũ mật, tức vị trí ban đầu của Mecho. Các dãy này có thể có độ dài bằng \(0\) nếu nhà của Mecho hoặc một tổ ong nằm kề vị trí ban đầu của chú. Ong không thể đi xuyên qua hoặc bay qua nhà của Mecho; đối với chúng, nhà cũng giống như một cái cây.

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa một số nguyên: số phút lớn nhất mà Mecho có thể tiếp tục ăn mật tại vị trí ban đầu mà vẫn về nhà an toàn.

Nếu Mecho không thể về tới nhà trước khi bị ong bắt, kể cả khi rời đi ngay lập tức, hãy in \(-1\).

Ràng buộc

• \(1 \le N \le 800\): độ dài cạnh của bản đồ.
• \(1 \le S \le 1\,000\): số bước tối đa Mecho có thể đi trong mỗi phút.

Phân nhóm

Một số bộ dữ liệu có tổng cộng \(40\) điểm thỏa mãn \(N \le 60\).

Ví dụ

7 3
TTTTTTT
TGGGGGT
TGGGGGT
MGGGGGD
TGGGGGT
TGGGGGT
THHHHHT

1

7 3
TTTTTTT
TGGGGGT
TGGGGGT
MGGGGGD
TGGGGGT
TGGGGGT
TGHHGGT

2

Nguồn

IOI 2009, ngày thi thứ hai: Mecho, bản tiếng Anh 1.1. Tác giả đề bài: Carl Hultquist. Tập đề bài và lời giải IOI 2009.