Problem C
Neutral Ground

Two kingdoms had been at war for a long time, until the emperor intervened to bring an end to the conflict. The territory in question comprises an $M$ by $N$ rectangular grid. At the emperor’s insistence, the two kings have withdrawn their troops until no two opposing troops are in adjacent squares of the map (adjacent being horizontal or vertical – diagonal is not considered).

The emperor proposes to designate certain squares of the map as neutral territory. Neither king will be allowed to move troops into those squares, and the emperor’s own forces will patrol them to be sure that both kings observe these rules.

The emperor is frugal and does not want to commit more soldiers to this effort than absolutely necessary. His generals have marked each square of the map with the number of soldiers required to secure that square. What remains is to choose which of those squares should be patrolled.

Write a program to determine the minimum number of soldiers that the emperor will need to be deploy to guarantee that the troops of one kingdom cannot move, in one or more steps, into squares occupied by the troops of the second kingdom (moving horizontally or vertically) without encountering the emperor’s own soldiers.

Input

Input begins with a line containing $2$ integers, $w$ and $h$, denoting the width and height of the map, where $1\le w,h\le 40$.

This is followed by $h$ lines. Each line contains $w$ characters, left justified. These characters will be ‘A’ or ‘B’, designating a position held by king A or king B, or a single numeric digit, designating a currently unoccupied position that can be secured by the use of that number of soldiers. For example, a ‘2’ would indicate that two soldiers must be deployed to that square to secure it against passage of other troops. A ‘0’ indicates terrain that is impassible – the emperor need not commit soldiers there because the kingdom troops cannot pass through that square.

No ‘A’ will be adjacent, horizontally or vertically, to any ‘B’.

There will be at least one ‘A’ and one ‘B’ in the input.

Output

Print a single line containing an integer denoting the minimum number of soldiers that the emperor must deploy to guarantee that there is no open path between any ‘A’ position and any ‘B’ position, using any combination of horizontal or vertical moves.

8 5
A11111AA
AA7B111A
111BB111
11BBB111
11BBB11B

13

25 6
A211111321231111111111111
2A2111110001111111BB11111
AA211111000111111BBBB1111
A2111114111411111BBBB1111
AA2111110001111111BB11111
AA21111110111111111111111

2