CF375C.Circling Round Treasures

You have a map as a rectangle table. Each cell of the table is either an obstacle, or a treasure with a certain price, or a bomb, or an empty cell. Your initial position is also given to you.

You can go from one cell of the map to a side-adjacent one. At that, you are not allowed to go beyond the borders of the map, enter the cells with treasures, obstacles and bombs. To pick the treasures, you need to build a closed path (starting and ending in the starting cell). The closed path mustn't contain any cells with bombs inside. Let's assume that the sum of the treasures' values that are located inside the closed path equals v, and besides, you've made k single moves (from one cell to another) while you were going through the path, then such path brings you the profit of v - k rubles.

Your task is to build a closed path that doesn't contain any bombs and brings maximum profit.

Note that the path can have self-intersections. In order to determine if a cell lies inside a path or not, use the following algorithm:

1. Assume that the table cells are points on the plane (the table cell on the intersection of the i-th column and the j-th row is point (i, j)). And the given path is a closed polyline that goes through these points.
2. You need to find out if the point p of the table that is not crossed by the polyline lies inside the polyline.
3. Let's draw a ray that starts from point p and does not intersect other points of the table (such ray must exist).
4. Let's count the number of segments of the polyline that intersect the painted ray. If this number is odd, we assume that point p (and consequently, the table cell) lie inside the polyline (path). Otherwise, we assume that it lies outside.

你有一张矩形表格形式的地图。表格的每个单元格要么是障碍物，要么是带有特定价值的宝物，要么是炸弹，要么是空单元格。你的初始位置也已给出。

你可以从地图的一个单元格移动到与其共享一条边的相邻单元格（即上、下、左、右四个方向）。在此过程中，你不允许移出地图边界，也不允许进入含有宝物、障碍物或炸弹的单元格。要拾取宝物，你需要构造一条闭合路径（起点和终点均为初始位置）。该闭合路径内部不能包含任何炸弹。假设闭合路径所围区域内的宝物总价值为 $v$，且你在遍历该路径过程中共进行了 $k$ 次单步移动（即从一个单元格移动到另一个相邻单元格），则该路径为你带来的收益为 $v - k$ 卢布。

你的任务是构造一条不包含任何炸弹、且收益最大的闭合路径。

注意：该路径允许自交。为了判断某个单元格是否位于路径内部，请使用如下算法：

1. 将表格单元格视为平面上的点（第 $i$ 列、第 $j$ 行的单元格对应平面点 $(i, j)$）；给定的路径是一条经过这些点的闭合折线。
2. 需要判断某个未被折线经过的表格点 $p$ 是否位于该折线内部。
3. 从点 $p$ 出发作一条射线，要求该射线不经过表格中其他任何格点（这样的射线一定存在）。
4. 统计该射线与折线各线段的交点个数。若交点个数为奇数，则认为点 $p$（从而对应表格单元格）位于折线（路径）内部；否则认为其位于外部。

The first line contains two integers n and m (1 ≤ n, m ≤ 20) — the sizes of the table. Next n lines each contains m characters — the description of the table. The description means the following:

• character "B" is a cell with a bomb;
• character "S" is the starting cell, you can assume that it's empty;
• digit c (1-8) is treasure with index c;
• character "." is an empty cell;
• character "#" is an obstacle.

Assume that the map has t treasures. Next t lines contain the prices of the treasures. The i-th line contains the price of the treasure with index i, v__i ( - 200 ≤ v__i ≤ 200). It is guaranteed that the treasures are numbered from 1 to t. It is guaranteed that the map has not more than 8 objects in total. Objects are bombs and treasures. It is guaranteed that the map has exactly one character "S".

第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 20$）—— 表格的尺寸。接下来的 $n$ 行，每行包含 $m$ 个字符 —— 表格的描述。该描述含义如下：

• 字符 "B" 表示一个含有炸弹的格子；
• 字符 "S" 表示起始格子，可假定该格子为空；
• 数字 $c$（$1$–$8$）表示编号为 $c$ 的宝藏；
• 字符 "." 表示一个空格子；
• 字符 # 表示一个障碍物。

假设地图上共有 $t$ 个宝藏。接下来的 $t$ 行给出各宝藏的价格。第 $i$ 行包含编号为 $i$ 的宝藏的价格 $v_i$（$-200 \leq v_i \leq 200$）。保证宝藏的编号为 $1$ 至 $t$。保证地图上总共至多有 $8$ 个“物体”，其中“物体”指炸弹和宝藏。保证地图中恰好有一个字符 "S"。

Print a single integer — the maximum possible profit you can get.

输出一个整数——你能获得的最大可能利润。

In the first example the answer will look as follows.

In the second example the answer will look as follows.

In the third example you cannot get profit.

In the fourth example you cannot get profit as you cannot construct a closed path with more than one cell.

在第一个例子中，答案如下所示。

在第二个例子中，答案如下所示。

在第三个例子中，你无法获得利润。

在第四个例子中，你无法获得利润，因为你无法用超过一个格子构造闭合路径。