两个王国长期交战，直到皇帝介入以结束冲突。相关领土由一个 $M \times N$ 的矩形网格组成。在皇帝的坚持下，两位国王撤回了他们的军队，直到地图上没有两支敌对的部队处于相邻的方格中（相邻指水平或垂直相邻，不考虑对角线）。

皇帝提议将地图上的某些方格指定为中立领土。任何一位国王都不允许将部队移入这些方格，皇帝的军队将巡逻这些区域以确保两位国王都遵守这些规则。

皇帝很节俭，不想在这一行动上投入超过绝对必要的士兵。他的将军们已经在地图的每个方格上标记了确保该方格安全所需的士兵人数。剩下的工作就是选择应该巡逻哪些方格。

编写一个程序，确定皇帝需要部署的最少士兵人数，以保证一个王国的部队无法在不遇到皇帝士兵的情况下，通过一步或多步（水平或垂直移动）进入第二个王国部队所占据的方格。

输入格式

输入的第一行包含两个整数 $w$ 和 $h$，分别表示地图的宽度和高度。$1 \le w, h \le 40$。

接下来是 $h$ 行。每行包含 $w$ 个左对齐的字符。这些字符可能是 'A' 或 'B'，表示国王 A 或国王 B 占据的位置；或者是一个数字，表示当前未被占据的位置，可以通过使用该数量的士兵来确保其安全。例如，'2' 表示必须在该方格部署两名士兵以防止其他部队通过。'0' 表示无法通行的地形——皇帝不需要在那里部署士兵，因为王国部队无法通过该方格。

没有任何 'A' 会与任何 'B' 水平或垂直相邻。

输入中至少会有一个 'A' 和一个 'B'。

输出格式

输出一行，包含一个整数，表示皇帝必须部署的最少士兵人数，以保证在任何 'A' 位置和任何 'B' 位置之间不存在通过水平或垂直移动组成的通路。

样例

样例输入 1

8 5
A11111AA
AA7B111A
111BB111
11BBB111
11BBB11B

样例输出 1

13

样例输入 2

25 6
A211111321231111111111111
2A2111110001111111BB11111
AA211111000111111BBBB1111
A2111114111411111BBBB1111
AA2111110001111111BB11111
AA21111110111111111111111

样例输出 2

2