你将获得一个 $N \times N$ 的填字游戏网格。每个格子要么是一个填有字母的白格，要么是一个黑格。同时，你还会获得一个包含 $M$ 个不同单词的字典，每个单词都有一个关联的分数。网格中的一个水平候选单词是指同一行中无法再向两端延伸的连续字母字符串。形式上，这意味着候选单词最左侧格子的左侧格子要么不存在，要么是黑格；最右侧格子的右侧格子同理。垂直候选单词的定义类似，只是字母位于同一列。水平候选单词从左到右读取，垂直候选单词从上到下读取。当且仅当每个候选单词都出现在给定的字典中时，该填字游戏才是有效的。有效填字游戏的分数是字典中与每个候选单词关联的分数之和。注意，两个或多个候选单词可能是相同的。在这种情况下，该单词的分数会相应地被多次累加。你需要编写一个程序来确定该填字游戏解的分数，如果无效，则输出 -1。

输入格式

输入包含多个测试用例。第一行包含一个正整数 $T$，表示测试用例的数量。

对于每个测试用例，第一行包含两个整数 $N, M$ ($1 \le N \le 1000, 1 \le M \le 4 \times 10^6$)，分别表示网格的大小和字典中单词的数量。接下来的 $N$ 行，每行包含一个长度为 $N$ 的字符串，其中每个字符要么是小写英文字母，要么是 '#'。如果第 $i$ 行的第 $j$ 个字符是 '#'，则表示第 $i$ 行第 $j$ 列的格子是黑格。否则，该字符表示填在该格子中的字母。接下来的 $M$ 行，每行包含一个仅由小写英文字母组成的非空字符串和一个正整数，表示字典中的一个单词及其分数。保证这 $M$ 个单词互不相同，每个单词的长度不超过 $N$，且每个单词的分数不超过 $10^9$。

保证所有测试用例中 $N^2$ 的总和不超过 $4 \times 10^6$，且所有测试用例中字典内单词总长度之和不超过 $4 \times 10^6$。

输出格式

对于每个测试用例，在一行中输出一个整数，表示如果填字游戏解有效，则输出其分数。如果解无效，则输出 -1。

样例

输入 1

2
2 4
ab
#d
ab 1
a 2
d 3
bd 4
2 4
ab
c#
ab 5
ca 2
b 6
c 7

输出 1

10
-1