10727번 - 룩과 구슬

당신은 체스를 아는가? 체스는 정사각형 격자의 각 칸에 말을 놓고 하는 게임의 일종이다. 체스에는 룩(Rook)이라는 말이 있다. 룩은 공격을 위해 한번 이동할 때 상하좌우에 있는 모든 칸을 이동할 수 있다. 아래 그림에서 빨간색으로 색칠된 칸들은 룩이 가로로 이동할 수 있는 칸이며, 파란색으로 색칠된 칸들은 룩이 세로로 이동할 수 있는 칸이다.

우리는 체스를 하려는 것은 아니지만, 룩을 사용한다. 우리는 \(N \times M\) 크기의 직사각형 격자판 위의 몇 개의 칸에 룩을 하나씩 놓았다. 거기에 더해서 몇 개의 장애물도 놓았다. 룩은 장애물을 뛰어넘을 수 없다. 따라서 아래 그림과 같이 룩의 위아래로 장애물이 놓여 있다면 룩이 세로로 이동하는 것은 불가능하다. 룩의 오른쪽 두 칸 옆에도 장애물이 있는데, 장애물에 닿기 전인 오른쪽 한 칸까지는 이동할 수 있다. 

현재 격자판 위에는 룩들이 한 번의 이동으로는 서로를 공격할 수 없도록 배치되어 있다. 룩과 장애물이 모두 없는 칸 위에는 숫자가 적혀 있으며, 이 칸에는 그 숫자 이하만큼의 구슬을 놓을 수 있다. 단, 구슬을 놓을 때는 각각의 룩이 가로로 공격할 수 있는 칸에 놓인 구슬 개수의 합과 세로로 공격할 수 있는 칸에 놓인 구슬 개수의 합이 같아야 한다. 구슬을 최대한 많이 놓으면 몇 개를 놓을 수 있을까?

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

다음 \(N\)개의 줄의 각 줄에는 길이가 \(M\)인 문자열이 하나씩 주어지는데, 이는 직사각형 판의 상태를 나타낸다. 이 문자열들은 'R', '#', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'로만 이루어져 있다. 'R'은 칸에 룩이 놓여 있음을 의미하며, '#'은 칸에 장애물이 놓여 있음을 의미하며, 이외의 숫자는 해당 칸 위에 놓을 수 있는 구슬 개수의 제한을 의미한다.

룩들은 한 번의 이동으로는 서로를 공격할 수 없도록 배치되어 있으며, 판에 배치된 룩의 개수는 70개를 넘지 않는다.

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