У Сережи есть прямоугольная таблица a размера n × m, в каждой ячейке которой находится нуль или единица. Сережа хочет, чтобы его таблица обладала следующим свойством: каждая компонента связности из одинаковых значений образует прямоугольник, стороны которого параллельны сторонам таблицы. Прямоугольники должны быть заполненными, другими словами, если компонента образует прямоугольник h × w, то она должна состоять из ровно hw ячеек таблицы.
Компонентой связности из одинаковых значений называется множество ячеек таблицы, удовлетворяющих свойствам:
- значения во всех ячейках одинаковые;
- ячейки множества образуют связную область в таблице (две ячейки связны, если они являются соседними в какой-то строке или в каком-то столбце таблицы);
- невозможно добавить ни одной ячейки в множество, не нарушив предыдущие два свойства.
Может ли Сережа поменять значения не более k ячеек таблицы на противоположное, чтобы таблица обладала описанным свойством? Какое минимальное количество ячеек таблицы при этом нужно изменить?
Выходные данные
Выведите -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
|
|
2
|
3 4 1
1 0 0 0
0 1 1 1
1 1 1 0
|
-1
|
|
3
|
3 4 1
1 0 0 1
0 1 1 0
1 0 0 1
|
0
|