시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

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

Опишем суть этой структуры данных. Квадродерево позволяет нам представлять в памяти матрицу размера $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$ элементов.

예제 입력 1

4 2
0001
0010
0000
0010

예제 출력 1

9

힌트

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

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