Paper Folding

You are given a rectangular sheet of paper divided into (N) rows and (M) columns of 1×1 cells. Each cell contains one integer.

You may fold the paper any number of times. In one fold, choose a line between two adjacent rows or between two adjacent columns, then fold one side onto the other. After a fold, if several cells overlap at the same position, the value at that position is the sum of the values written in those cells.

Considering every possible way to fold the paper, find the maximum value that can appear in any cell of the folded paper.

The first line contains the height (N) and width (M) of the paper. Both (N) and (M) are positive integers no greater than 12.

The next (N) lines each contain (M) integers, the values written in the cells. The absolute value of each integer is at most 100.

Print one integer: the maximum value that can appear in a cell.