该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

背景

　　17和他的小队逃出了魔法阵，来到了一个废旧的塔楼下。吃了经验的17为了防止再次触发什么奇奇怪怪的东西，决定自己一个人上塔寻宝。
　　这个塔总共有M层，每层有N个元素。这些元素包括：大门 D ，平地 . ，楼梯 H 和宝物 T 。
　　其中，大门 D 只会在第一层的某个位置有且只有一个，楼梯 H 每层有且仅有一个，宝物 T 若干，其余都是平地 . 。17发现在他进门后开始行动第一步的瞬间，塔楼开始晃动，17预测在S时间后，塔楼就会坍塌。请问17在保证安全脱离的情况下，最多可以拿到多少宝物。
　　只要经过宝物所在的位置就会自动拿到宝物，宝物被拿以后的那个位置就等同于平地。17可以花费1时间，从第K层的楼梯 H 到达第K+1层或第K-1层的楼梯 H 。17只能通过楼梯实现上下楼。楼梯和大门在不使用的时候即视作平地。

输入

第一行是三个正整数M，N，S。3<=M，N<=20。S<=100。
接下来是M行，每行N个字符。
保证只有 D . H T 这四个字符，且 H 每层有且只有一个，最后一行的某个位置是 D 。

输出

17在保证安全脱离的情况下，最多可以拿到的宝物数量。
17只要在最后一秒前到达大门就算安全脱离。

样例输入1

3 3 10
T.H
H.T
D.H

样例输出1

1

样例输入2

1 5 4
DTTTH

样例输出2

2

提示

在样例1中，拿到第二层的宝物后立即原路返回，时间刚好为10。

限制

时间：1s  内存：2048KB