중립 지대

두 왕국은 오랫동안 전쟁을 벌였고, 결국 황제가 나서서 분쟁을 끝내려 했다. 분쟁 지역은 $M \times N$ 크기의 직사각형 격자이다. 황제의 요구에 따라 두 왕은 한쪽 왕국의 병사가 다른 왕국의 병사와 상하좌우로 인접한 칸에 서지 않도록 병력을 물렸다. 대각선은 인접으로 보지 않는다.

황제는 지도의 일부 칸을 중립 지대로 지정하자고 제안한다. 두 왕은 그 칸에 병사를 들일 수 없고, 황제의 병력이 그곳을 순찰하며 두 왕이 규칙을 지키는지 감시한다.

황제는 검소해서 꼭 필요한 만큼만 병력을 투입하려 한다. 장군들은 각 칸을 확보하는 데 필요한 병사 수를 칸마다 표시해 두었다. 남은 일은 어느 칸을 순찰할지 고르는 것이다.

한쪽 왕국의 병사가 상하좌우로 한 번 이상 움직여 다른 왕국의 병사가 있는 칸에 황제의 병력과 마주치지 않고 도달하지 못하도록, 황제가 배치해야 할 병사의 최소 수를 구하는 프로그램을 작성하라.

첫 줄에는 지도의 너비 $w$와 높이 $h$를 나타내는 정수 두 개가 주어진다. 단, $1 \leq w, h \leq 40$이다. 이어지는 $h$개의 줄에는 왼쪽부터 $w$개의 문자가 적혀 있다. 각 문자는 다음 중 하나이다. 'A' 또는 'B'는 해당 왕의 병사가 있는 칸이다. 숫자 한 자리는 비어 있는 칸이며, 그 수만큼의 병사를 배치하면 확보할 수 있는 칸이다. 예를 들어 '2'는 그 칸을 막으려면 병사 두 명을 배치해야 한다는 뜻이다. '0'은 통과할 수 없는 지형이다. 병사가 지나갈 수 없으므로 황제는 그곳에 병사를 배치할 필요가 없다.

'A' 칸과 'B' 칸은 상하좌우로 인접하지 않는다. 입력에는 'A'와 'B'가 각각 하나 이상 있다.

상하좌우로만 이동해서 어떤 'A' 칸에서도 'B' 칸으로 열린 경로가 없도록 보장하는 데 필요한, 황제가 배치해야 할 병사의 최소 수를 한 줄에 정수로 출력한다.