Hôm nay là ngày 8.3 Quốc tế Phụ nữ, PuTuânitk20 muốn mua quà tặng cho mẹ và các bạn gái của mình. PuTuânitk20 đang ở cửa hàng lưu niệm để mua quà, sau đó anh sẽ lần lượt đi qua nhà của \(k\) người bạn gái để tặng rồi cuối cùng trở về nhà và tặng quà cho mẹ, đúng là con trai cưng của mẹ! Vì phải về nhà kịp trước bữa tối nên PuTuânitk20 muốn tìm cách đi nhanh nhất có thể.

Thành phố PuTuânitk20 đang ở được thể hiện qua một bảng kích thước \(m\times n\), mỗi ô vuông trong đó sẽ thể hiện một khu vực dân cư. Khu vực của cửa hàng PuTuânitk20 đang đứng sẽ được đánh dấu chữ T, nhà sẽ được đánh dấu chữ H, còn nơi ở của \(k\) người bạn gái sẽ được đánh dấu là G nằm rải rác trên bảng (không trùng nhau). Những nơi được đánh dấu chữ W thể hiện khu vực công trường đang thi công, không thể đi qua được. Những khu vực còn lại sẽ được thể hiện bằng dấu chấm ..

Tại mỗi khu vực ta có thể di chuyển sang các khu vực chung cạnh của nó trên bản đồ, và không thể di chuyển ra khỏi bản đồ (thành phố khác). Thời gian để di chuyển từ khu vực này sang khu vực khác sẽ tốn \(1\) đơn vị thời gian. Các bạn hãy giúp PuTuânitk20 tìm ra con đường ngắn nhất mà có thể đi qua nhà tất cả bạn nữ (có thể đi lặp lại những khu vực đã đi) và cuối cùng trở về nhà. Trên đường đi sang nhà các bạn nữ PuTuânitk20 vẫn có thể đi qua khu vực có nhà mình nhưng không về nhà, sau khi phát quà hết cho các bạn nữ thì PuTuânitk20 mới trở về nhà. Dữ liệu đảm bảo rằng luôn có cách để đi đến nhà các bạn gái (nghĩa là không có nhà bạn nào bị công trường vây quanh không có lối vào).

Input

• Dòng đầu chứa ba số nguyên \(M,\ N,\ K\) lần lượt là số hàng, số cột của bảng và số người bạn gái của PuTuânitk20.
• \(M\) dòng tiếp theo mỗi dòng sẽ gồm \(N\) ký tự được viết liền nhau thể hiện chi tiết bản đồ thành phố.

Output

• In ra một số nguyên duy nhất là tổng thời gian ít nhất mà PuTuânitk20 cần để có thể giao quà cho các bạn gái và trở về nhà với mẹ.

Ràng buộc

• Subtask 1 (\(60\%\) số test): \(5\leq M,\ N\leq500;\ 1\leq K\leq10\).
• Subtask 2 (\(40\%\) số test): \(5\leq M,\ N\leq500;\ 1\leq K\leq17\).

Ví dụ

Sample input

10 10 3
H....W....
.......W..
.W.W......
........G.
..WWWWW...
W.G...W..W
..W....W..
.....G.W..
.W..W.....
......W..T

Sample output

28

Giải thích ví dụ

Thứ tự giao quà tối ưu của PuTuânitk20 sẽ là: \((10,\ 10)\rightarrow(4,\ 9)\rightarrow(8,\ 6)\rightarrow(6,\ 3)\rightarrow(1,\ 1)\).