Trong một lần đi du lịch, Vũ vô tình bị lạc tại một hòn đảo hoang. Diện tích đảo là một hình chữ nhật \(n \times m\), biểu diễn như một ma trận. Tại mỗi ô trong đảo là một vật cản, một kho báu có giá trị nhất định, một quả bom, hoặc một ô trống. Bạn cũng biết được ô mà Vũ đang đứng. Nhưng rất xui cho anh bởi vì 1 tuần sau cơn bão \(\textbf{yagi}\) sẽ quét qua hòn đảo này, khi bão vào sẽ làm dâng nước biển lên vì vậy Vũ cần phải xây một tường chắn bắt đầu từ vị trí đang đứng của anh ta. Tiếp theo anh ta sẽ được quyền chọn 1 trong 4 ô kề cạnh với ô hiện tại và di chuyển qua đó xây bức tường tại ô đó và khi đứng trên ô nào phải bắt buộc phải xây tại ô đó (có thể xây đè lên ô đã xây). Và cuối cùng là quay lại vị trí anh ta đang đứng (tạo thành một đường đi khép kín). Lưu ý khi xây bức tường chỉ xây tại vị trí từ tâm của ô hiện tại sang tâm của ô tiếp theo (xem ví dụ để hiểu hơn)

• Vũ không được đi ra khỏi hòn đảo (biên của hình chữ nhật).
• Vũ không được phép đi qua ô mà có vật cản, bom và kho báu.
• Vũ được phép đi qua những ô đã qua.
• Khi tạo thành đường khép kín quả bom không được phép nằm trong đó. Hay nói cách khác khi nước dâng lên thì mọi quả bom đều phải nằm ở dưới nước và không được nằm trong bức tường mình vừa xây.

Nhiệm vụ của Vũ:

• Khi nước dâng lên, Vũ sẽ nhận được số vàng ở trong các ô kho báu khi nó nằm hoàn toàn bên trong bức tưởng chắn hay là đường khép kín(không tính trên cạnh hay trên bức tường);
• Gọi giá trị kho báu mà Vũ nhận được là \(p\) và số số lượt đi từ ô này sang ô khác là \(d\).
• Vũ phải xây sao cho giá trị \(p - d\) là lớn nhất.

Được biết tổng số ô chứa bom và ô chứa kho báu không vượt quá 8.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) \((1\leq n,m \leq 20)\) tương ứng với chiều dài và chiều rộng của đảo.
• Tiếp theo là \(n\) dòng với mỗi dòng là \(m\) kí tự với kí tự thứ \((i, j)\) là:
  • Kí tự B cho biết vị trí đó có bom.
  • Kí tự # cho biết vị trí đó có vật cản.
  • Kí tự . cho biết vị trí đó có là ô trống.
  • Kí tự S cho biết vị trí đó Vũ đang đứng và đó chắc chắn là ô trống.
  • Cuối cùng, kí tự từ 1 đến 9 chính là ô kho báu có thứ tự tương ứng, các số trong bảng luôn là phân biệt
  • Chú ý tổng số ô chứa bom và ô chứa kho báu không vượt quá 8.
• Dòng cuối cùng gồm các số \(a_i\) với \((-200 \le a_i \le 200)\) tương ứng với giá trị của kho báu thứ i.

Output

• Một số duy nhất là giá trị lớn nhất mà Vũ nhận được.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \times m \le 20\)
• Subtask \(2\) (\(15\%\) số điểm): cách đi tối ưu là luôn tạo thành duy nhất một hình chữ nhật.
• Subtask \(3\) (\(20\%\) số điểm): trên bản đồ chỉ tồn tại duy nhất một ô kho báu.
• Subtask \(4\) (\(15\%\) số điểm): bản đồ không chứa bom.
• Subtask \(5\) (\(30\%\) số điểm): không có ràng buộc gì thêm.

Examples

4 4 
2...
.1B.
..##
.S..
100 -50

0

4 5
2.#..
.....
..13.
.S...
100 -50 34

124

10 11
.3.....#...
...........
....6#..B..
#..........
...#.B.....
.S.......5.
........4..
#...#..2...
...........
..........1
2 56 46 -33 29 27

43