19883번 - Квадродерево 다국어

Одной из проблем, которые приходится решать любому программисту, является нехватка памяти, которую может использовать программа. Часто, чтобы уменьшить объем используемой программой памяти, программисты используют различные структуры данных, одной из которых и является квадродерево.

Опишем суть этой структуры данных. Квадродерево позволяет нам представлять в памяти матрицу размера $2^n\times{2^n}$, состоящую из нулей и единиц. Все дерево состоит из ячеек, каждая ячейка отвечает за некоторую часть этой матрицы, при этом каждая часть является квадратом со стороной $2^p$. Первая ячейка отвечает за всю матрицу.

Если все элементы квадрата, за который отвечает ячейка, имеют одинаковое значение ($0$ или $1$), то в ячейке просто хранится эта информация. Если же внутри квадрата существуют хотя бы два различных элемента, то весь квадрат делится на четыре непересекающихся квадрата со стороной $2^{p - 1}$, после чего для каждой четверти создается отдельная ячейка, и ссылки на все четыре созданных ячейки записываются в ячейку, отвечающую за большой квадрат.

Правильное квадродерево для данной матрицы. \\Любой квадрат, у которого все четыре стороны выделены, является ячейкой квадродерева.

Далеко не всегда подобный способ хранения матрицы приводит к сокращению объема памяти. Но не во всех задачах требуется абсолютно точно хранить всю матрицу, не потеряв значения ни одного элемента. Иногда можно потерять часть информации. А именно, разрешается изменить значения не больше, чем $k$ элементов матрицы.

Выясните, какое минимальное возможное количество ячеек может быть в квадродереве, описывающем матрицу, получающуюся из данной изменением не более, чем $k$ элементов.

Первая строка входного файла содержит два целых числа $t=2^n$ и $k$ --- размер матрицы и максимальное количество измененных ячеек соответственно ($4 \le t \le 128$, $1 \le k \le t^2$).

Гарантируется, что $t$ является степенью двойки.

Следующие $t$ строк содержат по $t$ символов, каждый из которых является $0$ или $1$. Эти строки описывают заданную матрицу.

Выведите в выходной файл одно целое число --- минимальное возможное количество ячеек в квадродереве, описывающем матрицу, получающуюся из данной изменением не более, чем $k$ элементов.

В приведенном примере можно, например, заменить две верхних единицы на нули. После этого получается матрица

Для ее хранения с помощью квадродерева необходимо 9 ячеек: одна для всей матрицы, четыре для четырех квадратов $2 \times 2$, три из них содержат 0, а четвертый, соответствующий нижнему правому углу, разбивается еще на четыре.