B. Сережа и таблица
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Сережи есть прямоугольная таблица a размера n × m, в каждой ячейке которой находится нуль или единица. Сережа хочет, чтобы его таблица обладала следующим свойством: каждая компонента связности из одинаковых значений образует прямоугольник, стороны которого параллельны сторонам таблицы. Прямоугольники должны быть заполненными, другими словами, если компонента образует прямоугольник h × w, то она должна состоять из ровно hw ячеек таблицы.

Компонентой связности из одинаковых значений называется множество ячеек таблицы, удовлетворяющих свойствам:

  • значения во всех ячейках одинаковые;
  • ячейки множества образуют связную область в таблице (две ячейки связны, если они являются соседними в какой-то строке или в каком-то столбце таблицы);
  • невозможно добавить ни одной ячейки в множество, не нарушив предыдущие два свойства.

Может ли Сережа поменять значения не более k ячеек таблицы на противоположное, чтобы таблица обладала описанным свойством? Какое минимальное количество ячеек таблицы при этом нужно изменить?

Входные данные

Первая строка содержит целые числа n, m и k (1 ≤ n, m ≤ 100; 1 ≤ k ≤ 10). Следующие n строк описывают таблицу a: i-я из них содержит m целых чисел ai1, ai2, ..., aim (0 ≤ ai, j ≤ 1) — элементы i-й строки таблицы.

Выходные данные

Выведите -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
Входные данные
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