Background

你是一名探险家，发现了一座神秘的岛屿。岛屿被划分成 n×m 的网格，每个格子有不同的地形类型（用字符表示）：

• 'S'：起点
• 'E'：终点
• '.'：平地（可通过）
• '#'：障碍（不可通过）
• 'T'：宝藏（可通过且拾取后价值+1）
• 'M'：怪物（可通过但会减少生命值）

你从起点出发，要到达终点。你有一个初始生命值 H。经过怪物格子会减少1点生命值，生命值不能为负。你需要找到一条从起点到终点的路径，使得：

1. 能够到达终点（生命值 ≥ 0）
2. 收集尽可能多的宝藏

问题描述

给定岛屿地图和初始生命值，求从起点到终点能收集的​最大宝藏数量​。如果无法到达终点，输出 -1。

Format

Input

• 第一行三个整数 n, m, H
  • 1 ≤ n, m ≤ 10
  • 1 ≤ H ≤ 10
• 接下来 n 行，每行 m 个字符，表示地图
  • 保证有一个'S'和一个'E'
  • 其他字符为 '.', '#', 'T', 'M' 中的一种

Output

• 输出最大宝藏数量
• 如果无法到达终点，输出 -1

Samples

4 5 3
S....
.TM#.
..#E.
.T...

2