Вам дано изображение, которое может быть представлено как 2-d таблица пикселей размера n на m. Каждый пиксель изображения либо включен, либо выключен, что обозначается символами «0» или «1», соответственно. Вы хотите сжать это изображение. Вы хотите выбрать целое число k > 1 и разбить изображение на блоки размера k на k. Если n и m не делятся на k, то изображение дополняется выключенными пикселями справа и снизу так, что размеры делятся на k. Все пиксели внутри одного блока должны иметь одинаковое значение. Данное изображение может быть не сжимаемым в текущем состоянии. Найдите минимальное число пикселей, которое нужно изменить так, чтобы изображение стало сжимаемым для некоторого k. Более точно, сначала вы должны выбрать k, затем изображение дополняется нулями, затем вы можете изменить некоторые пиксели так, чтобы изображение было сжимаемым для этого k.
Выходные данные
Выведите одно целое число — минимальное число пикселей, которое нужно изменить, чтобы изображение стало сжимаемым.
Примечание
Можно изменить символы, чтобы изображение стало следующим:
00110
00110
00000
Мы можем выбрать k = 2. Затем, изображение дополняется.
001100
001100
000000
000000
Видно, что его можно сжать для k = 2.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 5
00100
10110
11001
|
5
|