Numble 是一款类似于 Scrabble 的填字游戏，但使用的是数字。玩家手中有一组数字牌（1–9），需要使用手中牌的子集在棋盘上组成数字序列。有效数字序列的规则如下：
- 有效序列必须在行或列中（不能斜向）包含至少两张牌，且中间不能有空格，并且必须与棋盘上已有的一个或多个牌相连。
- 有效序列中的数字必须按非递增或非递减顺序排列。例如，“1467”、“7641”和“766641”是有效的，但“7461”无效。
- 有效序列中所有值的总和必须能被 3 整除。该总和是在应用任何来自奖励格的修正后计算的（见下文）。
与 Scrabble 棋盘类似，Numble 棋盘包含四种特殊类型的空格：
- 双倍和三倍数字格：将牌的数值加倍或变为三倍。该加倍或三倍后的值会被计入序列总和中，以判断总和是否能被 3 整除。
- 双倍和三倍序列格：将整个序列的数值加倍或变为三倍（在应用了单个牌的加倍或三倍修正之后）。注意，三倍序列格总是会使任何数值序列的总和成为 3 的倍数。
一个序列可能会命中多个特殊空格，从而叠加奖励。例如，如果一个序列同时覆盖了双倍序列格和三倍序列格，则该序列的总分乘以 6。
玩家的一步操作包括将手中的一组牌放置到棋盘上的空位中，横跨单行或单列。所创建的牌行或牌列中不能有空位，但可以跳过棋盘上已有的牌。一旦牌放置完毕，所有与新放置的牌相交的牌行和牌列都必须构成有效序列。玩家可以获得所形成的所有序列的分数。注意，只有放置在奖励格上的牌才会触发奖励——任何已经覆盖在奖励格上的牌不会重复获得奖励。
图 H.1 展示了一个示例棋盘和一系列移动，其中“d”和“t”代表双倍和三倍数字分格，“D”和“T”代表双倍和三倍序列分格。
图 H.1: (a) 初始棋盘。(b) 放置 6, 4, 2 后。(c) 放置 7, 7, 6, 2 后。(d) 放置 1, 1, 9 后。
初始棋盘如图 H.1a 所示。第一步放置 6, 4 和 2，如图 H.1b 所示，得分为 $6 \times 2 + 5 + 4 \times 2 + 2 = 27$ 分。下一步放置 7, 7, 6 和 2，如图 H.1c 所示，形成了多个有效序列——一个水平序列和三个垂直序列。水平序列得分为 $7 + 7 \cdot 2 + 6 \cdot 3 + 4 + 2 = 45$，三个垂直序列分别得分为 $1 + 7 \cdot 2 = 15$、$3 + 6 \cdot 3 = 21$ 和 $7 + 2 = 9$（注意所有四个形成的序列总和均为 3 的倍数）。此步总得分为 $45 + 15 + 21 + 9 = 90$ 分。最后一步放置 1, 1 和 9，横跨双倍和三倍序列格。垂直序列得分为 $(1 + 1 \cdot 2 + 7 + 9) \cdot 2 \cdot 3 = 114$，水平序列得分为 $1 \cdot 2 + 1 + 3 + 5 + 7 = 18$，总得分为 132 分（这对应于样例输入 1）。
给定棋盘和手中的牌，求出单次操作可能获得的最大分数。
输入格式
输入以两个正整数 $r$ 和 $c$ ($r, c \le 20$) 开始，表示棋盘的行数和列数。 接下来是 $r$ 行，每行包含 $c$ 个字符，由空格分隔。每个字符为以下之一：
- 一个数字，表示棋盘上已有的牌
- ‘-’，表示一个空位
- ‘d’ 或 ‘t’，表示一个空的双倍或三倍数字格
- ‘D’ 或 ‘T’，表示一个空的双倍或三倍序列格
棋盘上始终至少有一个数字，且棋盘上的数字行和列是连通的，并遵循非递减/非递增序列规则。（棋盘上的序列可能不遵循被 3 整除的规则，因为它们可能覆盖了奖励格）。
接下来是一个正整数 $t$ ($t \le 10$)，表示手中的牌数，随后是 $t$ 个 1 到 9 之间的数字，指定牌的值。
输出格式
输出在单次操作中使用提供的棋盘和牌所能获得的最大分数。
样例
样例输入 1
4 5 D - - 6 - d 1 3 5 7 7 7 6 4 2 T - - 2 - 5 1 1 7 7 9
样例输出 1
132
样例输入 2
4 5 D - - 6 - d 1 3 5 7 7 7 6 4 2 T - - 2 - 5 1 1 6 7 9
样例输出 2
150