Dino 已经为一场包裹快递比赛练习了几个星期。在比赛中，最快将所有包裹从仓库运送到指定目的地的参赛者将获得冠军。不幸的是，Dino 只有两只手，所以他一次最多只能携带两个包裹。
只要一次携带不超过两个包裹，他可以随意放下和拿起包裹。他也可以按任何顺序携带和运送它们，并且每个包裹可以运送到任何目的地。在完成他的送货路线后，每个 $k$ 个目的地都必须有一个包裹。
在比赛期间，Dino 在一个 $n$ 行 $m$ 列的网格上移动，其中空地用 . 标记，障碍物用 # 标记，Dino 的起点以及所有包裹的位置用 S 标记，包裹目的地用 X 标记。在一秒钟内，他可以向四个方向（上、下、左、右）移动到任何不是障碍物的相邻单元格。放下和拿起包裹所花费的时间可以忽略不计。
帮助 Dino 确定将所有包裹运送到目的地并返回起点所需的最少秒数，如果不可能，则输出 -1。
输入格式
第一行包含三个自然数 $n$、$m$ 和 $k$（$1 \le n, m \le 500$，$1 \le k \le 67$），分别表示网格的行数、列数以及包裹目的地的数量。
接下来的 $n$ 行中，每行包含 $m$ 个字符 $c_{ij}$，用于描述网格。网格中的每个字符都将是 .、#、S 或 X 之一（不带引号）。
字母 X 在网格中将恰好出现 $k$ 次。
输出格式
输出单行一个整数，表示 Dino 将所有包裹运送到目的地并返回起点所需的最少秒数，如果不可能，则输出 -1。
子任务
| 子任务 | 分数 | 限制条件 |
|---|---|---|
| 1 | 17 | $k = 2$ |
| 2 | 26 | $k \le 16$ |
| 3 | 29 | $k \le 22$ |
| 4 | 38 | 无附加限制。 |
样例
输入样例 1
5 5 3 X...X ..... ..... ..... S...X
输出样例 1
24
样例 1 说明
Dino 将携带 1 个包裹前往右下角的目的地，放下包裹，然后返回标记有字母 S 的单元格。接着他将携带 2 个包裹，依次前往右上角和左上角的目的地。之后，他将返回起点，在 24 秒内完成他的路线。
输入样例 2
5 5 4 ..X.. #X#.. #...X .SX#. .....
输出样例 2
16