407355: GYM102770 C Crossword Validation

A crossword is a word puzzle that usually takes the form of a square or a rectangular grid of white- and black-shaded cells. The game's goal is to fill the white cells with letters, forming words or phrases, by solving clues, which lead to the answers. The answer words and phrases are typically placed in the grid from left to right and from top to bottom. The shaded cells are used to separate the words or phrases. Crossword grids such as those appearing in most North American newspapers and magazines feature solid areas of white cells. Every letter is checked (i.e. is part of both an "across" word and a "down" word) and usually each answer must contain at least three letters. In such puzzles, shaded cells are typically limited to about one-sixth of the total. Crossword grids elsewhere, such as in Britain, South Africa, India and Australia, have a lattice-like structure, with a higher percentage of shaded cells, leaving about half the letters in an answer unchecked. For example, if the top row has an answer running all the way across, there will often be no across answers in the second row.

Crossword puzzles have a long history. The title for the world's first crossword puzzle is disputed, but most people believe the crossword puzzle is invented in the 19th century. With the emergence of personal computers, more and more crossword puzzles are distributed online instead of on newspapers and books. Software that aids in creating and solving crossword puzzles has been written since at least 1976. In this problem, you are to write a program that checks if a solution for a crossword puzzle is valid. Note that the rules of the puzzle in this problem, which is described in the next paragraph, may differ from the real-world ones.

You are given a completed crossword puzzle on a $$$N \times N$$$ grid. Each cell is either a white cell filled with a letter or a black cell. You are also given a dictionary of $$$M$$$ distinct words, where each word has a score associated with it. A horizontal candidate word in the grid is a continuous string of letters on the same row of the grid that can't be extended. Formally, this means that the cell to the left of the leftmost cell of the candidate word either doesn't exist or is a black cell, and the same goes for the cell to the right of the rightmost cell. Vertical candidate words are defined similarly, except that the letters are on the same column. Candidate words are read from left to right for horizontal words or from top to bottom for vertical words. The crossword puzzle is valid if and only if each candidate word is present in the given dictionary. The score of a valid puzzle is the sum of the scores in the dictionary associated with each candidate word. Note that two or more candidate words may be the same. In this case, the score of that word is added multiple times accordingly. Your program must determine the score of the solution, or report that it is not valid.

The input contains multiple cases. The first line of the input contains a single positive integer $$$T$$$, the number of cases.

For each case, the first line of the input contains two integers $$$N, M \ (1 \le N \le 1\,000, 1 \le M \le 4\times 10^6)$$$, the size of the grid and the number of words in the dictionary. The following $$$N$$$ lines each contain a string of length $$$N$$$, where each character is either a lowercase English letter or '#'. If the $$$j$$$-th character of the $$$i$$$-th string is '#', then the cell located in the intersection of the $$$i$$$-th row and the $$$j$$$-th column is a black cell. Otherwise, this character denotes the letter filled in that cell. The following $$$M$$$ lines each contain a non-empty string consisting of only lowercase English letters, and a positive integer, denoting a word in the dictionary and its score. It is guaranteed that those $$$M$$$ words are pairwise distinct, the length of each word doesn't exceed $$$N$$$, and the score of each word doesn't exceed $$$10^9$$$.

It is guaranteed that the sum of $$$N^2$$$ over all cases doesn't exceed $$$4\times 10^6$$$, and the sum of the lengths of all words in the dictionary over all cases doesn't exceed $$$4\times 10^6$$$.

For each case, print a single integer in a single line, the score of the crossword solution given in the input if it is valid. If the solution is not valid, print $$$-1$$$ instead.

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

10
-1