Problem H
Numble

Numble is a crossword game that is similar to Scrabble, but with numbers. The player has a hand of tiles with digits on them ($1$–$9$) and needs to make sequences of numbers using a subset of the tiles in hand to place on the board. The rules of a valid number sequence are:

• A valid sequence has to have at least two tiles in a straight line without spaces in a row or column (never diagonally) and must be connected to one or more tiles already on the board

• The numbers in a valid sequence must be arranged in non-increasing or non-decreasing order. Sequences “$1467$”, “$7641$” and “$766641$” are valid, but “$7461$” is not.

• The total of all values in a valid sequence must be divisible by $3$. This is calculated after any modifications given from bonus spaces (see below)

Like a Scrabble board, the Numble board contains four special types of spaces:

• double and triple number spaces double or triple the numerical value of a tile. This doubled or tripled value is counted in the total of the sequence to see if the total is divisible by $3$.

• double and triple sequence spaces double or triple the entire value of the sequence (after individual tiles are doubled or tripled, if any). Note that a triple sequence space will always make any sequence of values a multiple of three.

It’s possible for a sequence to hit multiple special spaces which compounds the bonus. For example, if a sequence covers both a double sequence space and a triple sequence space, the total value of the sequence is multiplied by $6$.

A player’s move consists of laying down a set of tiles from their hand onto empty spaces on the board across a single row or column. The row or column of tiles created cannot have an empty space in it, but can skip over tiles already on the board. Once the tiles are placed, all rows and columns of tiles that intersect with the newly placed tiles must form a valid sequence. A player scores for all sequences that are formed. Note that only sequences that place a tile over a bonus space scores the bonus — any already-placed tile that is covering a bonus does not score the bonus a second time.

Figure 1 shows a sample board and a series of moves, where “d” and “t” represent double and triple number score spaces and “D” and “T” represent double and triple sequence score spaces.

Figure 1: (a) Initial board. (b) After playing $6,4,2$. (c) After playing $7,7,6,2$. (d) After playing $1,1,9$.

The initial board is shown in 1a. The first move places a $6, 4$ and $2$ as shown in 1b scoring $6\times 2 + 5 + 4\times 2 + 2 = 27$ points. The next move places $7, 7, 6$ and $2$ as shown in 1c, forming multiple valid sequences — one horizontal and three vertical. The horizontal sequence scores $7+7\cdot 2+6\cdot 3+4+2 = 45$ and the three vertical sequences score $1+7\cdot 2 =15$, $3+6\cdot 3 = 21$ and $7+2 = 9$ (notice that all four sequences formed total to multiples of $3$). Overall this play is worth $45+15+21+9=90$ points. The final move places $1, 1$ and $9$ across both a double and triple sequence space. The score for the vertical sequence is $(1 + 1\cdot 2 + 7 + 9) \cdot 2 \cdot 3 = 114$ and the score for the horizontal sequence is $1\cdot 2+1+3+5+7= 18$ for a total score of $132$ points (this corresponds to Sample Input $1$).

Given a board and a hand of tiles, what is the maximum possible score that can be made?

Input

The input begins with two positive integers $r$ $c$ ($r,c \leq 20$), the number of rows and columns on the board. After this are $r$ rows of $c$ characters, separated by spaces. Each character is either:

• a digit, representing a tile already on the board

• ‘-’, representing an empty space

• ‘d’ or ‘t’, representing an empty double or triple number space

• ‘D’ or ‘T’, representing an empty double or triple sequence space

There will always be at least one digit on the board, and the rows and columns of digits of the board will be connected, and follow the non-decreasing/non-increasing sequence rules. (Sequences on the board may not follow the divisible by $3$ rule because they may be covering bonus tiles).

There will then follow a positive integer $t$ ($t \leq $ 10), the number of tiles in hand, and then $t$ digits between $1$ and $9$ specifying the tile values.

Output

Output the maximum score that can be made in a single turn using the board and tiles provided.

4 5
D - - 6 -
d 1 3 5 7
7 7 6 4 2
T - - 2 -
5
1 1 7 7 9

132

4 5
D - - 6 -
d 1 3 5 7
7 7 6 4 2
T - - 2 -
5
1 1 6 7 9

150