Pasha 正在玩一款名为“DiaBro III”的电子游戏。他正在游戏中与 $n \cdot m$ 个怪物战斗。这些怪物排列成 $n$ 行 $m$ 列。行号从 $1$ 到 $n$ 编号，列号从 $1$ 到 $m$ 编号。

每个怪物属于 $k$ 种类型之一。第 $i$ 种怪物类型由两个整数 $q_i$ 和 $g_i$ 描述：Pasha 只有在经验值至少为 $q_i$ 时才能击杀该类型的怪物，且每击杀一个该类型的怪物，Pasha 将获得 $g_i$ 点经验值。

Pasha 想要通过确定四个整数 $r_1, r_2, c_1$ 和 $c_2$ 来选择一个矩形，满足 $1 \le r_1 \le r_2 \le n$ 且 $1 \le c_1 \le c_2 \le m$。然后，Pasha 开始击杀所选矩形内的怪物——即位于满足 $r_1 \le r \le r_2$ 且 $c_1 \le c \le c_2$ 的单元格 $(r, c)$ 上的怪物。起初，他没有任何经验值。如果能够以某种顺序击杀矩形内的所有怪物，且不击杀任何矩形外的怪物，则称该矩形是“好的”。

你需要编写一个程序，计算有多少种不同的“好的”矩形。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 200$)，分别表示怪物的行数和列数。

接下来的 $n$ 行，每行包含恰好 $m$ 个小写拉丁字母。第 $i$ 行的第 $j$ 个字符表示位于第 $i$ 行第 $j$ 列的怪物类型。相同类型的怪物用相同的小写拉丁字母表示。

下一行包含一个整数 $k$ ($1 \le k \le 26$)，表示怪物类型的数量。

接下来的 $k$ 行，每行包含某种怪物类型的描述。第 $i$ 种怪物类型的描述由字符 $l_i$（对应此怪物类型的小写拉丁字母）以及两个整数 $q_i$ 和 $g_i$ ($0 \le q_i \le 10^9, 1 \le g_i \le 10^9$) 组成，分别表示击杀该类型怪物所需的经验值和击杀每个该类型怪物后获得的经验值。$l_i, q_i$ 和 $g_i$ 的值由空格分隔。

保证输入中不存在未被描述的怪物类型。

输出格式

输出仅包含一个整数——满足上述所有条件的 $r_1, r_2, c_1$ 和 $c_2$ 的选择方案数。

样例

输入 1

2 3
aba
baa
2
a 0 2
b 4 100

输出 1

11

输入 2

4 6
aaaaaa
abbaaa
aaacba
aaabba
3
a 0 1
b 3 2
c 12 5

输出 2

128

说明

在第一个样例中，共有 11 种可能的 $r_1, r_2, c_1$ 和 $c_2$ 取值：

1. $r_1 = 1, r_2 = 1, c_1 = 1, c_2 = 1$;
2. $r_1 = 1, r_2 = 1, c_1 = 1, c_2 = 3$;
3. $r_1 = 1, r_2 = 1, c_1 = 3, c_2 = 3$;
4. $r_1 = 1, r_2 = 2, c_1 = 1, c_2 = 2$;
5. $r_1 = 1, r_2 = 2, c_1 = 1, c_2 = 3$;
6. $r_1 = 1, r_2 = 2, c_1 = 2, c_2 = 3$;
7. $r_1 = 1, r_2 = 2, c_1 = 3, c_2 = 3$;
8. $r_1 = 2, r_2 = 2, c_1 = 1, c_2 = 3$;
9. $r_1 = 2, r_2 = 2, c_1 = 2, c_2 = 2$;
10. $r_1 = 2, r_2 = 2, c_1 = 2, c_2 = 3$;
11. $r_1 = 2, r_2 = 2, c_1 = 3, c_2 = 3$.