Delicious Cake Division

Yangyang is a little foodie who adores many foods but dislikes some. One day, he found a freshly baked rectangular cake at home. The cake is partitioned into n×m unit pieces, and each piece is scored by Yangyang according to how delicious he finds it. A higher score means he likes that piece more, and a lower score means he dislikes it.

Before eating, Yangyang must score each of the n×m unit cake pieces. Then he is allowed to choose some cake blocks to eat under the following rules:

1. The cake is of size \( n\times m \). It is first divided into \( n\times m \) unit pieces. Each unit piece gets a score representing its deliciousness.
2. Each unit piece is either eaten entirely or not eaten at all.
3. If Yangyang decides to eat a set of unit pieces, they must form a sub-cake block (a rectangle or square) whose sides are parallel to the original cake's borders. The deliciousness of such a block is the sum of the scores of the unit pieces that form it.
4. Any number of blocks (of any valid size) may be chosen.
5. To maintain the cake's aesthetic appearance, the positions of any two eaten cake blocks (in the original cake) must not be adjacent; that is, no two eaten blocks may touch each other (sharing a common side) and they must not overlap. (See Figures 1 and 2 for invalid selections and Figures 3 and 4 for valid selections.)
6. The overall goal is to maximize the sum of the deliciousness values of the eaten cake blocks.

Your task is to help Yangyang decide which cake blocks to eat in order to maximize the total deliciousness sum, while obeying all the above rules. Note that a single unit cell is considered a valid rectangle.

The problem can be mathematically formulated as follows. Let the cake be represented as a matrix \( A \) of size \( n\times m \) where \( A_{i,j} \) is the score of the unit cell at row \( i \) and column \( j \). You want to choose a collection of submatrices \( \{(r_1^k, c_1^k, r_2^k, c_2^k)\} \) (with \( 1\le r_1^k\le r_2^k\le n \) and \( 1\le c_1^k\le c_2^k\le m \)) such that:

• For any two different chosen submatrices, if you expand one submatrix by one unit in all four directions (within the cake bounds), it does not intersect the other submatrix. This ensures that the blocks are not adjacent.
• The sum of all scores in the chosen submatrices is maximized.

Note: It is always allowed to choose no block at all, resulting in a total deliciousness sum of 0.

inputFormat

The first line contains two integers \( n \) and \( m \) (the dimensions of the cake).

Then follow \( n \) lines, each containing \( m \) integers. The \( j \)-th number in the \( i \)-th line represents \( A_{i,j} \), the score for the cell in the \( i \)-th row and \( j \)-th column.

You may assume that \( n \) and \( m \) are small (for example, \( n, m \leq 6 \)) so that a brute-force/backtracking solution is feasible.

outputFormat

Output a single integer: the maximum total deliciousness sum that Yangyang can achieve by selecting appropriate cake blocks to eat under the given rules.

sample

2 2
1 2
3 4

10