Sereja and Table
Description
Sereja has an n × m rectangular table a, each cell of the table contains a zero or a number one. Sereja wants his table to meet the following requirement: each connected component of the same values forms a rectangle with sides parallel to the sides of the table. Rectangles should be filled with cells, that is, if a component form a rectangle of size h × w, then the component must contain exactly hw cells.
A connected component of the same values is a set of cells of the table that meet the following conditions:
- every two cells of the set have the same value;
- the cells of the set form a connected region on the table (two cells are connected if they are adjacent in some row or some column of the table);
- it is impossible to add any cell to the set unless we violate the two previous conditions.
Can Sereja change the values of at most k cells of the table so that the table met the described requirement? What minimum number of table cells should he change in this case?
The first line contains integers n, m and k (1 ≤ n, m ≤ 100; 1 ≤ k ≤ 10). Next n lines describe the table a: the i-th of them contains m integers ai1, ai2, ..., aim (0 ≤ ai, j ≤ 1) — the values in the cells of the i-th row.
Print -1, if it is impossible to meet the requirement. Otherwise, print the minimum number of cells which should be changed.
Input
The first line contains integers n, m and k (1 ≤ n, m ≤ 100; 1 ≤ k ≤ 10). Next n lines describe the table a: the i-th of them contains m integers ai1, ai2, ..., aim (0 ≤ ai, j ≤ 1) — the values in the cells of the i-th row.
Output
Print -1, if it is impossible to meet the requirement. Otherwise, print the minimum number of cells which should be changed.
Samples
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
3 4 1
1 0 0 0
0 1 1 1
1 1 1 0
-1
3 4 1
1 0 0 1
0 1 1 0
1 0 0 1
0