Sereja 有一个 n × m 的矩形表 a,表的每个单元格包含一个零或一个数字一。 Sereja 希望他的表格满足以下要求:相同值的每个连通分量形成一个矩形,其边与表格的边平行。矩形应该充满单元格,也就是说,如果一个组件形成一个大小为 h × w 的矩形,那么该组件必须恰好包含 hw 个单元格。
相同值的连通分量是满足以下条件的表格单元格的集合:
- 该集合中的每两个单元格具有相同的值;
- 集合中的单元格在表格上形成一个连通区域(如果两个单元格在表格的某行或某列中相邻,则它们是连通的);
- 除非我们违反前面的两个条件,否则不可能将任何单元格添加到集合中。
Sereja 能否更改表格中最多 k 个单元格的值,以使表格满足所描述的要求?在这种情况下,他应该更改的最小表格单元格数量是多少?
输入
第一行包含整数 n、m 和 k (1 ≤ n, m ≤ 100; 1 ≤ k ≤ 10)。接下来的 n 行描述表 a:其中第 i 行包含 m 个整数 ai1、ai2、...、aim (0 ≤ ai, j ≤ 1) — 第 i 行单元格中的值。
输出
如果无法满足要求,则打印-1。否则,打印应更改的最小单元格数。
示例
输入 #1
5 5 2 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1
输出 #1
1
输入 #2
3 4 1 1 0 0 0 0 1 1 1 1 1 1 0
输出 #2
-1
输入 #3
3 4 1 1 0 0 1 0 1 1 0 1 0 0 1
输出 #3
0