URI Online Judge | 1543

Board With Prizes

By Cristhian Bonilha, UTFPR BR Brazil

Timelimit: 1

You are at a television program, and there is a huge chance for you to win a lot of money. You are there to play a game, with some peculiar rules, and the resulting amount of money depends on your smartness, where you may even lose money if you play badly.

The game works as follows: there is a board, with N lines and M columns, and in each cell of this board there is a positive integer, representing an amount of money. At each cell you can choose one of the following signs to put there:

Life would be too easy if you could choose to put the '+' sign at all positions, so there are two additional rules to the game: for each row of the board, you must fill the cells with one of a few patterns of signs made by the game producers; and for each column of the board, it's not allowed for two vertical adjacent cells to have the same sign (applies to the signs '+' and '-'). It is possible to use the same pattern more than once, since it doesn't disrespect the second rule above.

See an example in the picture below, where the patterns are: “++”, “--”, “.+” e “+.”.

Consider that there is always at least one way to fill the board.

As the game is new, they let you use your computer to help you make the decision, without knowing that you were a programmer. Write an algorithm that tells you what is the maximum amount that is possible to achieve in the game.

Input

There are several test cases. Each test case starts with two integers, N and M (1 ≤ N, M ≤ 100), indicating the number of lines and columns of the board, respectively.

Following there will be N lines, containing M integers each, representing the values from the board. Be v the value of any cell of the board, 1 ≤ v ≤ 100.

Following there will have an integer K (1 ≤ K ≤ 100), indicating the number of patterns. After that, there will be K lines, each containing M characters, representing each of the patterns, as the symbology given above.

The last test case is indicated when N = M = 0, which should not be processed.

Output

For each test case print one line, containing one integer, representing the maximum amount that is possible to achieve in the game if the patterns are choosen in an optimal way.

Sample Input Sample Output

2 2
3 4
1 2
4
++
--
+.
.+
3 3
1 3 2
4 2 3
3 5 1
2
+.+
-+-
0 0

5
8