Paper Pieces

Youngsun has a rectangular sheet of paper with digits written on it. The sheet is divided into $1 \times 1$ square cells, and each cell holds exactly one digit. Rows are numbered from top to bottom and columns from left to right.

Youngsun wants to cut the sheet into non-overlapping pieces. Each piece is a rectangle whose height or width is 1. A piece of length $N$ represents an $N$-digit number. A horizontal piece reads its digits from left to right, and a vertical piece reads its digits from top to bottom.

The figure below shows one way to cut a $4 \times 4$ sheet.

From top to bottom, the rows of the sheet in the figure are 4937, 2591, 3846, and 9150. With this cut, the sum of the pieces is $493 + 7160 + 23 + 58 + 9 + 45 + 91 = 7879$.

Write a program that cuts the sheet so that the sum of the pieces is as large as possible.

The first line contains the height $N$ and the width $M$ of the sheet. ($1 \le N, M \le 4$)

Each of the next $N$ lines contains one row of the sheet as $M$ digits with no spaces. Every digit is between 0 and 9.

Print the maximum sum of the pieces that Youngsun can obtain.