Description

Are you tired of playing Pac-Man on your phone? Recently, the MOKIA phone launched a new game called “Enclosing Beans.” Give it a try.

The rules are simple. In an $N\times M$ grid there are $D$ beans, and each bean has a value $V_i$. The player may choose any cell as the starting cell. Each move, the player may go to one of the four orthogonally adjacent cells, and eventually must return to the starting cell. The final score is the total value of all beans enclosed by the path minus the number of steps taken. Some cells contain obstacles; at no time may the player enter a cell that contains an obstacle or a bean. The player’s minimum possible score is $0$, i.e., they may choose to do nothing.

Note the notion of being enclosed: a bean is considered enclosed if it lies inside the polygon formed by the path (which may be a complex polygon with self-intersections). See the two examples below:

In the first example, the bean lies inside the rectangle formed by the path, so it is enclosed. In the second example, even though the path visits the $8$ neighboring cells around the bean, the interior of the polygon formed by the path does not contain the bean, so it is not enclosed.

Bubu has become obsessed with this game but cannot get a high score. You decide to write a program to help him pass the game.

Input Format

The first line contains two integers $N$ and $M$, the dimensions of the grid.

The second line contains an integer $D$, the total number of beans.

The third line contains $D$ integers $V_1$ to $V_D$, the values of the beans.

Then follow $N$ lines, each with $M$ characters, forming an $N\times M$ character matrix describing the game grid. Character 0 denotes an empty cell, # denotes an obstacle, and digits 1 to 9 denote beans with the corresponding indices.

Output Format

Output a single integer, the maximum possible score.

3 8
3
30 -100 30
00000000
010203#0
00000000

38

Hint

$50\%$ of the testdata satisfies $1\le D\le 3$.

$100\%$ of the testdata satisfies $1\le D\le 9$, $1\le N,M\le 10$, $-10^4\le V_i\le 10^4$.

Translated by ChatGPT 5