Roma 在智能手机上下载了一款带有 RPG 元素的现代策略游戏。在游戏中，玩家使用回合制机制指挥三个角色并与成群的敌人战斗。由于该游戏是共享软件，而 Roma 是一个从不在游戏上花钱的严肃家伙，因此这款游戏对他来说只能在非常受限的模式下运行。

行动步数受到严格限制，敌人不会移动，敌人和角色都不会死亡，但游戏结束时的得分仍然会显示。正如 Roma 从他尝试玩这款游戏的经历中发现的那样，得分由以下部分组成：角色对敌人造成的伤害总和加上角色受到的治疗量总和，减去敌人对角色造成的伤害总和以及角色对敌人进行的治疗量总和。Roma 想要刷新每个关卡的绝对最高纪录。而你将要帮助他！

游戏地图是一个大小为 $N \times M$ 的矩形网格。某些格子被敌人占据，某些格子被不可逾越的障碍物占据，还有三个格子被 Roma 的三个角色占据，其余所有格子都是空闲的。游戏进程按以下方式进行：Roma 先行动，然后是全能的人工智能行动。在 Roma 的回合中，他选择角色行动的顺序，然后依次让这些角色行动，一个接一个地进行。在角色的行动中，Roma 可以移动该角色，然后使用其技能之一。角色通过水平或垂直方向的单步移动（每步一格）来进行移动，使得总移动步数不超过该角色的耐力值（stamina）。角色不能穿过不可逾越的障碍物、敌人或其他角色。Roma 也可以选择完全不移动该角色，或者不使用其任何技能，或者对该角色不进行任何操作。在 Roma 的回合结束后，敌人开始行动，人工智能会试图最小化玩家的得分。然后开始新的一轮，或者游戏结束。

每个角色的技能是以下之一：

• TELEPORT L：角色可以瞬间移动到游戏地图上与当前格子曼哈顿距离不超过 $L$ 的任意空闲格子。
• SWAP L：角色可以与当前格子曼哈顿距离不超过 $L$ 的任意其他角色交换位置。
• SINGLE ATTACK r R d：角色对距离其当前位置曼哈顿距离不小于 $r$ 且不大于 $R$ 的任意一个选定格子造成 $d$ 点基础伤害。
• SPLASH ATTACK r R d：角色对距离其当前位置曼哈顿距离不小于 $r$ 且不大于 $R$ 的所有格子造成 $d$ 点基础伤害。
• SINGLE HEAL r R d：角色对距离其当前位置曼哈顿距离不小于 $r$ 且不大于 $R$ 的任意一个选定格子恢复 $d$ 点生命值。
• SPLASH HEAL r R d：角色对距离其当前位置曼哈顿距离不小于 $r$ 且不大于 $R$ 的所有格子恢复 $d$ 点生命值。

每种类型的敌人是以下之一：

• SINGLE r R d：敌人对距离其当前位置曼哈顿距离不小于 $r$ 且不大于 $R$ 的任意一个选定格子造成 $d$ 点基础伤害。
• SPLASH r R d：敌人对距离其当前位置曼哈顿距离不小于 $r$ 且不大于 $R$ 的所有格子造成 $d$ 点基础伤害。

每个敌人对造成的伤害有三个乘数：它对第一个角色造成 $d \cdot M_1$ 的伤害，对第二个角色造成 $d \cdot M_2$ 的伤害，对第三个角色造成 $d \cdot M_3$ 的伤害。此外，每个敌人对受到的伤害也有三个乘数：来自第一个角色的伤害乘以 $S_1$，来自第二个角色的伤害乘以 $S_2$，来自第三个角色的伤害乘以 $S_3$。

由于游戏是在硬核（hardcore）难度下进行的，角色之间可以互相造成伤害（造成基础伤害值），也可以治疗敌人，但敌人之间不会互相造成伤害。

两个位置之间的曼哈顿距离是这两个位置的行号差的绝对值与列号差的绝对值之和。

你需要计算 Roma 在给定的游戏中能获得的最大得分。

输入格式

输入的第一行包含四个整数 $N, M, D$ 和 $K$：游戏地图的尺寸、游戏进行的轮数（回合数）以及关卡中敌人的类型数量 $K$ ($1 \le N, M, D \le 8$, $0 \le K \le 26$)。

接下来的 $N$ 行给出游戏地图。每行包含恰好 $M$ 个字符：

• “.” 表示该格子为空；
• “#” 表示该格子不可通行；
• “1”、“2” 或 “3” 表示三个角色的初始位置；
• “A”..“α”（其中 $\alpha$ 是英文字母表中的第 $K$ 个大写字母）表示地图上敌人的类型。

保证地图上恰好有字符 “1”、“2” 和 “3” 各一个。

接下来的 $K$ 行给出敌人类型的描述。首先是伤害类型（字符串 SINGLE 或 SPLASH），然后是九个数字 $r, R, d, M_1, M_2, M_3, S_1, S_2, S_3$ ($0 \le r \le R \le 20$, $1 \le d, M_1, M_2, M_3, S_1, S_2, S_3 \le 1000$)。第一行描述对应类型 “A”，第二行对应类型 “B”，依此类推。

然后给出三个角色的描述。在每个角色描述的第一行，包含两个整数：$V$（角色的耐力值）和 $A$（其技能数量）($0 \le V \le 5$, $0 \le A \le 100$)。接下来的 $A$ 行描述技能，移动类技能的格式为 “技能名称 L” ($0 \le L \le 5$)，其他技能的格式为 “技能名称 r R d” ($0 \le r \le R \le 20$, $1 \le d \le 1000$)。

输出格式

输出一个整数：Roma 在给定的游戏中能获得的最大得分。

样例

输入样例 1

4 4 1 1
....
.12.
....
AA3A
SINGLE 0 1 10 1 1 100 10 10 1
1 2
SPLASH HEAL 0 3 4
TELEPORT 1
1 2
SINGLE ATTACK 0 10 10
SWAP 2
1 1
SPLASH ATTACK 1 1 1000

输出样例 1

1984

输入样例 2

1 6 8 2
123#BA
SINGLE 5 5 10 1000 100 1 1 1 1
SINGLE 2 2 5 300 1 100 1 1 1
5 1
SINGLE ATTACK 5 5 1
5 1
SPLASH HEAL 1 1 1
5 2
SPLASH ATTACK 0 1 100
SWAP 2

输出样例 2

-5574