## 题目背景

暑假集训期间，学校的一部分道路正在施工。为了保证安全，老师给每位同学发放了若干张临时通行证。同学们从宿舍出发前往教室时，普通道路可以直接通过，施工区域不能进入，而检查点需要消耗一张通行证才能通过。

现在给出一张校园平面图，请你帮助同学计算从起点到终点的最短路。

## 题目描述

校园可以看成一个 $n$ 行 $m$ 列的网格。每个格子为以下字符之一：

- `S`：起点，恰好出现一次；
- `T`：终点，恰好出现一次；
- `.`：普通道路，可以直接通过；
- `#`：施工区域，不能进入；
- `P`：检查点，进入该格子时需要消耗一张通行证。

同学一开始有 $K$ 张通行证。每次可以向上、下、左、右相邻的一个格子移动一步，不能走出地图，也不能进入 `#`。

每次进入一个 `P` 格子都会消耗一张通行证。如果已经没有足够的通行证，就不能进入 `P` 格子。`S` 和 `T` 不会消耗通行证。

请你求出从 `S` 到 `T` 的最少移动步数。如果无法到达，输出 $-1$。

## 输入格式

第一行包含三个整数 $n,m,K$，表示地图行数、列数和初始通行证数量。

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

## 输出格式

输出一行，包含一个整数。

如果可以到达终点，输出最少移动步数；否则输出 $-1$。

## 输入输出样例 #1

### 输入 #1


5 7 1
  
S..P..T
  
###.###
  
.......
  
#######
  
.......
  


### 输出 #1


6


## 说明/提示

对于样例 $1$，可以从起点沿第一行向右走，进入检查点 `P` 时消耗 $1$ 张通行证，然后继续到达终点。总共移动 $6$ 步。

对于样例 $2$，没有通行证，不能进入第一行的检查点 `P`。一种最短路线是先向下走到底行，绕过中间障碍后再从右侧回到终点，总共移动 $8$ 步。

对于所有测试数据，保证：

- $1 \le n,m$
- $n \times m \le 2 \times 10^5$
- $0 \le K \le 10$
- 地图中恰好有一个 `S` 和一个 `T`
- 地图中只包含字符 `S`、`T`、`.`、`#`、`P`

本题共 $40$ 个测试点，其中第 $1 \sim 20$ 个测试点每个 $2$ 分，第 $21 \sim 40$ 个测试点每个 $3$ 分。

| 测试点编号 | 数据范围或特殊性质 |
| --- | --- |
| $1 \sim 8$ | 地图中没有 `P` |
| $9 \sim 16$ | $K=0$ |
| $17 \sim 24$ | $n,m \le 30$ |
| $25 \sim 32$ | $K=1$ |
| $33 \sim 40$ | 无特殊性质 |

注意本体卡线性数组，用vector