Du Lịch Đảo

Có một lưới $R\times C$ gồm các ô: X (đảo), S (nước nông), . (nước sâu). Các ô X liên thông (theo 4 hướng) tạo thành một đảo. Có tổng cộng $N$ đảo.

Bessie xuất phát từ một đảo bất kỳ và muốn thăm tất cả $N$ đảo. Di chuyển giữa các đảo phải đi qua các ô S (không thể đi qua .). Chi phí di chuyển là số ô S phải bơi qua.

Tìm tổng chi phí bơi tối thiểu để thăm tất cả các đảo.

Dữ liệu vào

• Dòng $1$: Hai số nguyên $R$ và $C$.
• $R$ dòng tiếp: Mỗi dòng gồm $C$ ký tự (X, S, hoặc .).

Dữ liệu ra

Một số nguyên — tổng chi phí bơi tối thiểu.

Ràng buộc

• $1\le N\le 15$ (số đảo)
• $1\le R,C\le 50$

Ví dụ