T412502 SFLS 的校园

 在 SFLS 校园里每一个同学都必须给老师们问好，这是 SFLS 学子必要的“素养”。 人缘很广的我，从教室去到机房遇到了很多问题。~~因此，我要来折磨你。~~

我们可以将 SFLS 校园看做 $n$ 行 $m$ 列的地图 $a_{i,j}$ 其中: - ``.`` 代表空地，可以走。 - ``#`` 代表墙，不可以走。 - ``T`` 代表老师，每一个人都得向老师问好，问好的时间为 $s$。即到达这个点需要再花费 $s$ 的时间。 - ``S`` 代表同学，他们都是我的朋友，我可以选择是否与他交流，若与他交流需要耗费一定时间，**每个朋友只能交流一次**。 - ``B`` 为起点，即教室。 - ``E`` 为终点，即机房。 Z 老师要求我们必须在 $t$ 时间内到达机房（到达机房的时间小于等于 $t$）可是我又想在一路上与更多的朋友交流。 请你求出当到达机房的时间小于等于 $t$ 时，我最多可以跟多少个朋友交流。 在行走的过程中，可以上下左右四个方向走，各需要 $1$ 的单位时间。若遇到老师，还必须向老师问好。

数据来自标准输入，保证所有输入的数为整数。 第一行 $n,m,s,k$ 和 $t$。 其中 $n,m,s,t$ 具体意义见题目表述，$k$ 表示图中朋友的个数。 接下来一个 $n$ 行 $m$ 列的字符矩阵 $a$，包含 ``.#TSBE`` 六种字符。 接下来包含 $k$ 行输入。 每一行包含三个整数 $x,y,z$。代表第 $x$ 行 $y$ 列的朋友需要交流 $z$ 时间。

如果能顺利到达机房，那么输出能与朋友交流的最大次数和在此情况下到达机房的最短时间（必须小于等于 $t$）。 如果不能顺利到达机房或到达机房的最短时间大于 $t$，输出 `AK IOI`。

#### 数据范围 对于 $100 \%$ 的数据，保证 $1 \le n,m \le 500$，$0 \le s \le 100$，$0 \le k \le 18$，$0 \le t \le 2 \times 10^5$，$1 \le x,y \le n$，$0 \le z \le 500$。 **本题采用捆绑测试**，子任务及数据点分配如下： | 子任务编号 | $n \leq$ | $m\leq$ | $s\leq$ | $k\leq$ | 分值 | | :--------: | :------: | :-----: | :-----: | :-----: | :--: | |$1$| $5$ | $5$ | $100$ | $10$ | $20$ | | $2$ | $100$ | $100$ | $0$ | $10$ | $8$ | | $3$ | $100$ | $100$ | $100$ | $1$ | $12$ | | $4$ | $100$ | $100$ | $100$ | $10$ | $20$ | | $ 5 $ | $500$ | $500$ | $100$ | $18$ | $40$ |