Rooks and Marbles

A rook in chess picks one of the four directions (up, down, left, right) and travels as far as it likes in a single move.

You are given an $N \times M$ rectangular grid. Some squares hold one rook each, and some squares hold an obstacle. A rook cannot jump over an obstacle. In any direction it stops on the square just before the obstacle, and it never leaves the board. The squares a rook reaches in one move are its attack range. The squares it reaches to the left and to the right are the horizontal attack range, and the squares it reaches upward and downward are the vertical attack range.

The rooks on the board are placed so that no rook attacks another in one move. Every square that holds neither a rook nor an obstacle carries a digit, and you can place at most that many marbles on the square. When you place marbles, every rook must see the same number of marbles on both axes: the marbles in its horizontal attack range and the marbles in its vertical attack range have to add up to the same total.

Place as many marbles as you can. Find the largest number of marbles the board can hold.

The first line contains two integers $N$ and $M$ ($1 \le N, M \le 50$), separated by a space, the size of the board.

Each of the next $N$ lines contains one string of length $M$ describing the board. The strings consist only of R, #, and the digits 0 to 9. R is a square with a rook, # is a square with an obstacle, and a digit is the largest number of marbles that square can hold.

The rooks are placed so that no rook attacks another in one move, and the board holds at most 70 rooks.

Print the largest number of marbles the board can hold on the first line.