← 返回题目列表

Codeforces · 425/B

B. Sereja 和桌子

中文机器翻译题面 查看原题

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