Thử thách trên đảo

Trong một trò chơi điện tử, nhân vật của bạn phải vượt qua một thử thách trên một hòn đảo: ghé thăm tất cả các ngôi đền trên đảo.

Hòn đảo được mô tả bởi một bảng hình chữ nhật $R\times C$. Mỗi ô của bảng là núi, đền hoặc đất trống. Đền được ký hiệu bởi ký tự S, núi bởi ký tự #, đất trống bởi ký tự .. Núi rất cao và nguy hiểm nên nhân vật không thể đi vào các ô núi, chỉ có thể đi vào ô đền hoặc ô đất trống.

Ban đầu nhân vật đứng ở ô $(1,1)$, ô này chắc chắn là đất trống. Khi đang ở ô $(i,j)$, nhân vật chỉ có thể di chuyển sang một trong các ô $(i+1,j)$, $(i-1,j)$, $(i,j+1)$, $(i,j-1)$ và không được rời khỏi đảo. Mỗi bước di chuyển mất $1$ đơn vị thời gian. Đi qua một ô đền nghĩa là đã ghé thăm ngôi đền đó.

Để chiến thắng, nhân vật phải ghé thăm cả $N$ ngôi đền trong thời gian ít nhất. Cho bản đồ hòn đảo, hãy tìm thời gian ít nhất đó.

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên dương $R$, $C$, $N$ ($1\le R,C\le 100$, $1\le N\le 15$).
• $R$ dòng tiếp theo, mỗi dòng gồm $C$ ký tự thuộc ., #, S, lần lượt là đất trống, núi và đền. Bản đồ có đúng $N$ ký tự S, và ô $(1,1)$ chắc chắn là đất trống.

Dữ liệu ra

In ra một số nguyên là thời gian ít nhất để ghé thăm cả $N$ ngôi đền. Nếu không có cách nào, in ra $-1$.

Ràng buộc

• $1\le R,C\le 100$
• $1\le N\le 15$

Ví dụ