Dino xuất phát tại ô S của một bảng, nơi có các kiện hàng. Mỗi ô X là một đích cần giao đúng một kiện. Mỗi lần Dino mang được nhiều nhất hai kiện, có thể nhặt hoặc đặt kiện không tốn thời gian, và đi một ô kề cạnh không bị chặn trong một giây. Hãy tìm thời gian nhỏ nhất để giao đủ hàng đến mọi ô X và quay lại S, hoặc -1 nếu không thể.

Dữ liệu vào

Dòng đầu chứa \(n,m,k\) (\(1\le n,m\le500\), \(1\le k\le67\)). \(n\) dòng tiếp theo mô tả bảng với các ký tự ., #, S, X; ký tự X xuất hiện đúng \(k\) lần.

Dữ liệu ra

In thời gian nhỏ nhất để hoàn thành và trở về ô xuất phát, hoặc -1.

Ràng buộc

Các giới hạn chính thức của dữ liệu được nêu đầy đủ trong phần Dữ liệu vào.

Phân nhóm

1. \(17\) điểm: \(k=2\).
2. \(26\) điểm: \(k\le16\).
3. \(29\) điểm: \(k\le22\).
4. \(38\) điểm: không có ràng buộc thêm.

Ví dụ

5 5 3
X...X
.....
.....
.....
S...X

24

5 5 4
..X..
#X#..
#...X
.SX#.
.....

16

Nguồn

COCI 2025/2026 - Vòng 2, bài Natjecanje.

Đề bài, dữ liệu kiểm thử và lời giải tham khảo được lấy từ nguồn chính thức của Croatian Open Competition in Informatics.