Description

Partition an $a \times b$ numeric matrix as follows: cut the original matrix along a straight line into two matrices, then continue partitioning the resulting matrices in the same way (you may also choose to partition only one of them). After $(n - 1)$ cuts, the original matrix is partitioned into $n$ matrices. Each cut may only be made along the gaps between numbers (i.e., along the grid lines between cells).

Each position in the original matrix has a score. The total score of a matrix is the sum of the scores at all positions it contains. Now, you need to partition the matrix into $n$ matrices according to the above rule, minimizing the mean square deviation of the total scores of the matrices.

Given the matrix and $n$, write a program to compute the minimal value of the mean square deviation.

Input Format

The first line contains 3 integers, the values of $a, b, n$ $(1 < a, b, n \le 10)$.

From the second line to the $(a + 1)$-th line, each line contains $b$ non-negative integers less than $100$, representing the score at the corresponding position in the matrix. Adjacent numbers in each row are separated by a single space.

Output Format

Output a single number: the minimal mean square deviation, rounded to two decimal places.

5 4 4
2 3 4 6
5 7 5 1
10 4 0 5
2 0 2 3
4 1 1 1

0.50

Hint

Translated by ChatGPT 5