您有一张矩形表格形式的地图。表格中的每个单元格要么是障碍物,要么是具有一定价格的宝藏,要么是炸弹,要么是空单元格。你的初始位置也是给你的。
您可以从地图的一个单元格转到一侧相邻的单元格。此时,你不能越过地图边界,进入有宝藏、障碍物和炸弹的牢房。要拾取宝藏,您需要构建一条闭合路径(在起始单元格中开始和结束)。封闭路径不得包含任何装有炸弹的单元。假设位于闭合路径内的宝藏价值之和等于 v,此外,您在经过该路径时进行了 k 个单次移动(从一个单元格到另一个单元格),那么该路径将为您带来 v - k 卢布的利润。
你的任务是建造一条不包含任何炸弹并带来最大利润的封闭路径。
请注意,路径可以有自相交。为了确定单元格是否位于路径内,请使用以下算法:
1. 假设表格单元格为平面上的点(第i列与第j行交点处的表格单元格为点(i, j))。给定的路径是经过这些点的闭合折线。
2. 需要判断表格中未与折线相交的点 p 是否位于折线内部。
3. 让我们画一条从点 p 开始且不与表格中其他点相交的射线(这样的射线必须存在)。
4. 让我们计算一下与绘制的射线相交的多段线的线段数。如果这个数字是奇数,我们假设点 p(以及表格单元格)位于折线(路径)内。否则,我们假设它位于外面。
输入
第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 20) — 表的大小。接下来的 n 行每行包含 m 个字符——表的描述。描述含义如下:
- 角色“B”是一个带有炸弹的单元格;
- 字符“S”是起始单元格,您可以假设它是空的;
- 数字c(1-8)是索引为c的宝藏;
- 字符“.”是一个空单元格;
- 字符“#”是障碍物。
假设地图上有t个宝藏。接下来的 t 行包含宝藏的价格。第 i 行包含索引为 i, vi (- 200 ≤ vi ≤ 200) 的宝藏的价格。保证宝物的编号是从1到t。保证地图上的物体总数不超过8个。物体是炸弹和宝藏。保证地图上恰好有一个字符“S”。
输出
打印一个整数——您可以获得的最大可能利润。
示例
输入 #1
4 4 .... .S1. .... .... 10
输出 #1
2
输入 #2
7 7 ....... .1###2. .#...#. .#.B.#. .3...4. ..##... ......S 100 100 100 100
输出 #2
364
输入 #3
7 8 ........ ........ ....1B.. .S...... ....2... 3....... ........ 100 -100 100
输出 #3
0
输入#4
1 1 S
输出#4
0
注意
在第一个示例中,答案如下所示。
在第二个示例中,答案如下所示。
在第三个示例中,您无法获得利润。
在第四个示例中,您无法获得利润,因为您无法构建具有多个单元格的闭合路径。