|Codeforces Round #221 (Div. 1)|
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:
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:
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".
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.