题目内容

游乐场举办寻宝活动，活动区域划分为 $n$ 行 $m$ 列的小格。参与者从入口出发，沿上下左右相邻的格子移动，途中可以捡钥匙、开门并收集藏在格子里的纪念币。

地图中恰有一个起点 S 和一个终点 T，其余格子为普通地面 .、不能进入的围栏 #、钥匙 K、锁门 D 或纪念币 C。玩家需从 S 出发到达 T，每个格子最多经过一次，并遵守以下规则：

• 进入 K 格子可获得一把钥匙；
• 进入 D 格子必须消耗一把已有钥匙；
• 进入 C 格子可收集一个宝箱；
• 整条路线最多经过 $k$ 个门；
• # 格子不能进入。

求到达终点时最多能收集多少个宝箱。若无法到达终点，输出 $-1$。

输入描述

第一行输入三个整数 $n$、$m$ 和 $k$。

接下来 $n$ 行，每行一个长度为 $m$ 的字符串，表示地图。

约束

$1 \le n,m \le 8$

$0 \le k \le 10$

地图中恰有一个 S 和一个 T

地图中 K、D、C 的总数不超过 $12$

输出描述

输出一个整数，表示能够收集的最多宝箱数；若无法到达终点，输出 $-1$。

样例1

输入

4 5 1
S.K#C
..D.C
C#..T
.....

输出

2

说明

一条可收集两个宝箱的路线为 $(1,1)\to(2,1)\to(3,1)\to(4,1)\to(4,2)\to(4,3)\to(3,3)\to(3,4)\to(2,4)\to(2,5)\to(3,5)$。路线经过 $(3,1)$ 和 $(2,5)$ 两个宝箱格，且没有经过门或重复格子，最终到达 $T$。地图只有这两个宝箱，因此最多收集 $2$ 个。

样例2

输入

5 5 1
S....
.###.
.#T#.
.#D#.
.....

输出

-1

说明

终点被石墙围住，只能从正下方的门 $(4,3)$ 进入；但整张地图上没有钥匙 K，无法消耗钥匙开门，因此无法到达终点，输出 $-1$。