Maximum Sum Submatrix with Row Rearrangement

You are given a matrix of integers with n rows and m columns. You are allowed to rearrange the rows in any order. After rearrangement, you need to find the maximum sum of any contiguous submatrix. A submatrix is defined as a rectangular block of cells spanning consecutive rows and consecutive columns.

More formally, if the rearranged matrix is \(B\) then for some \(1 \leq i \leq j \leq n\) and \(1 \leq k \leq l \leq m\), the sum of the submatrix is given by:

[ S = \sum_{r=i}^{j}\sum_{c=k}^{l} B_{r,c} ]

Your task is to compute the maximum possible value of \(S\) over all choices of row permutation and all contiguous submatrices of the rearranged matrix.

Note: Because of the row permutation, the order of rows is not fixed. You must consider all possible row orders. The input matrices will be small enough such that a brute force approach (evaluating all row permutations) works within reasonable time.

inputFormat

The input is read from standard input (stdin) and has the following format:

<n> <m>
a1,1 a1,2 ... a1,m
...
 an,1 an,2 ... an,m

Here, n is the number of rows and m is the number of columns. The next n lines each contain m integers representing the rows of the matrix.

outputFormat

Output a single integer representing the maximum sum of any contiguous submatrix that can be obtained after rearranging the rows. The output should be printed to standard output (stdout).

## sample

3 3
1 2 1
2 3 2
3 4 3

21