Problem J
Quad Tree
One of the problems that any programmer has to solve is the lack of memory that a program can use. Often, to reduce the amount of memory used by the program, programmers use various data structures, one of which is the Quad Tree.
Let’s describe this data structure. A Quad Tree is built on a matrix of size $2^n \times 2^n$, consisting of zeros and ones. The tree consists of nodes, each node is responsible for a certain part of this matrix, and each part is a square with a side of $2^p$. The topmost node is responsible for the entire matrix.
If all elements of the square for which the node is responsible have the same value ($0$ or $1$), then the node simply stores this value. However, if there are at least two different elements within the square, the entire square is divided into four non-overlapping squares with a side of $2^{p - 1}$, after which a separate node is created for each quarter, and references to all four created nodes are recorded in the node responsible for the large square.
Any square, whose all four sides
are highlighted, is a cell of the quad tree.
Such method of storing a matrix does not always lead to a reduction in memory usage. However, not all problems require absolutely precise storage of the entire matrix without losing the value of any element. Sometimes, it is allowed to lose part of the information. Specifically, we can change the values of no more than $k$ elements of the matrix.
Determine the minimum possible number of nodes that can be in the Quad Tree built on a matrix obtained by changing no more than $k$ elements.
Input
The first line of the input contains two integers $t=2^n$ and $k$ — the size of the matrix and the maximum number of changed cells, respectively ($2 \le t \le 128$, $1 \le k \le t^2$).
It is guaranteed that $t$ is a power of two.
The next $t$ lines contain $t$ characters each, each of which is $0$ or $1$. These lines describe the given matrix.
Output
Output a single integer — the minimum possible number of nodes in the Quad Tree describing the matrix obtained by changing no more than $k$ elements.
Notes
In the provided example, for instance, you can replace the two upper ones with zeros. After that, the resulting matrix is
To store it using a quad tree, $9$ nodes are needed: one for the entire matrix, four for the four $2 \times 2$ squares, three of which contain 0, and the fourth, corresponding to the lower right corner, is further divided into four.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 2 0001 0010 0000 0010 |
9 |