룩과 구슬

체스의 룩은 한 번 이동할 때 자기 칸에서 상하좌우 네 방향 중 하나를 골라 원하는 만큼 갈 수 있다.

$N \times M$ 크기의 직사각형 격자판이 있다. 몇 개의 칸에는 룩을 하나씩 놓았고, 몇 개의 칸에는 장애물을 놓았다. 룩은 장애물을 뛰어넘지 못한다. 어느 방향으로 가든 장애물을 만나면 장애물 바로 앞 칸까지만 갈 수 있고, 판 밖으로 나갈 수도 없다. 룩이 한 번의 이동으로 갈 수 있는 칸을 그 룩의 공격 범위라고 하자. 그중 왼쪽과 오른쪽으로 갈 수 있는 칸이 가로 공격 범위, 위쪽과 아래쪽으로 갈 수 있는 칸이 세로 공격 범위이다.

판 위의 룩은 한 번의 이동으로는 서로를 공격할 수 없도록 놓여 있다. 룩도 장애물도 없는 칸에는 숫자가 하나씩 적혀 있고, 그 칸에는 적힌 숫자 이하만큼의 구슬을 놓을 수 있다. 단, 구슬을 놓을 때는 각 룩마다 가로 공격 범위에 놓인 구슬 개수의 합과 세로 공격 범위에 놓인 구슬 개수의 합이 같아야 한다.

구슬을 최대한 많이 놓으려고 한다. 판 위에 놓을 수 있는 구슬 개수의 최댓값을 구하라.

첫째 줄에 판의 크기를 나타내는 두 정수 $N$, $M$ ($1 \le N, M \le 50$)이 공백으로 구분되어 주어진다.

둘째 줄부터 $N$개의 줄에 걸쳐 길이가 $M$인 문자열이 한 줄에 하나씩 주어지며, 이는 판의 상태를 나타낸다. 문자열은 R, #, 그리고 0부터 9까지의 숫자로만 이루어져 있다. R은 룩이 놓인 칸, #은 장애물이 놓인 칸을 뜻하고, 숫자는 그 칸에 놓을 수 있는 구슬 개수의 상한을 뜻한다.

룩은 한 번의 이동으로는 서로를 공격할 수 없도록 놓여 있고, 판에 놓인 룩의 개수는 70개를 넘지 않는다.

첫째 줄에 판 위에 놓을 수 있는 구슬 개수의 최댓값을 출력한다.