[HAOI2007]分割矩阵

给定一个 $a\times b$ 的数字矩阵，每个位置都有一个分值。一个子矩阵的总分等于其中所有位置的分值之和。

每次可以沿数字之间的缝隙，用一条直线将一个矩阵分割成两个矩阵。对于分割后得到的矩阵，可以继续进行同样的分割，也可以只选择其中一部分继续分割。经过 $n-1$ 次分割后，原矩阵将被分成 $n$ 个矩阵。

请按照上述规则将原矩阵分割成 $n$ 个矩阵，使这些矩阵总分的均方差最小，并求出该最小值。

输入格式

第一行包含 $3$ 个整数 $a,b,n$，分别表示矩阵的行数、列数以及需要分割得到的矩阵数量。

接下来 $a$ 行，每行包含 $b$ 个小于 $100$ 的非负整数，表示矩阵中对应位置的分值。每行相邻两个数之间用一个空格分隔。

输出格式

输出一个数，表示均方差的最小值，四舍五入保留小数点后 $2$ 位。

样例输入

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

数据范围

• $1<a,b\le 10$；
• $1<n\le 10$；
• $n\le a\times b$；
• 矩阵中每个位置的分值均为小于 $100$ 的非负整数。

来源与许可

本题为 HAOI 2007 试题「分割矩阵」，题面与测试数据整理自 BZOJ。

样例 1

输入

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