题目背景

本题满分 $110$。

题目描述

在一个 $n\times m$ 的网格上，有 $k$ 个包裹要配送到 $k$ 个不同的格子上。包裹起初在中转站处。

有以下四种格子：

• .：空格子。
• #：障碍物。
• S：中转站。
• X：包裹要被配送到的格子。

已知：同时至多能带两个包裹；每秒可以向四连通（上下左右）的格子移动一格，但是不能移动到障碍物格子上或者越界。

请求出将所有包裹配送并回到中转站的最短时间，或报告无解。

输入格式

第一行，三个正整数 $n,m,k$（$1\le n,m\le 500$，$1\le k\le 67$）。

接下来 $n$ 行，第 $i$ 行一个长度为 $m$ 的字符串 $s_i$，字符集为 $\{\texttt{.},\texttt{\#},\texttt{S},\texttt{X}\}$。$s_{i,j}$ 表示第 $i$ 行第 $j$ 列的格子的类型。

特别地，保证 $\texttt{X}$ 出现恰好 $k$ 次。

输出格式

若无解，输出一行 $-1$。

否则输出一个正整数，表示答案。

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

24

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

16

提示

样例解释

样例一解释：先带着一个包裹配送到右下角，回到中转站；然后带着两个包裹依次配送到左上、右上，最后回到起点。

子任务

• $\text{Subtask 1 (17 pts)}$：$k\le 2$；
• $\text{Subtask 2 (26 pts)}$：$k\le 16$；
• $\text{Subtask 3 (29 pts)}$：$k\le 22$；
• $\text{Subtask 4 (38 pts)}$：无额外限制。