Matrix Partitioning for Minimum Variance

You are given a matrix of size \(a\times b\) filled with integers. Each cell has a value. You must partition the matrix into \(n\) rectangular pieces using \(n-1\) splitting operations. Each splitting operation must cut a current rectangle along one of the gaps between numbers (i.e. along a row or column boundary), thereby dividing it into two smaller rectangles. At each step you may choose to split any one of the available rectangles. After \(n-1\) splits, the original matrix is divided into \(n\) rectangles.

\n

Let the sum of the numbers in each rectangle be \(S_i\) for \(i=1,2,\ldots,n\), and let the total sum of the matrix be \(T\). We define the variance of the sums as

\n\[ Var = \frac{1}{n}\sum_{i=1}^{n}S_i^2 - \left(\frac{T}{n}\right)^2. \]

Your task is to partition the given matrix (by choosing the splitting lines and the order of splits) so that the above variance is minimized, and then output the minimum variance value.

inputFormat

The first line contains three integers \(a\), \(b\), and \(n\) where \(a\) and \(b\) are the number of rows and columns of the matrix, and \(n\) is the number of pieces you must split the matrix into.

\n

The following \(a\) lines each contain \(b\) integers, representing the matrix.

outputFormat

Output a single line containing the minimum variance (as defined above) achievable by splitting the matrix as described. The answer should be printed with 6 decimal places.

sample

2 2 2
1 2
3 4

1.000000