쿼드트리

프로그래머라면 누구나 마주치는 문제 중 하나는 프로그램이 사용할 수 있는 메모리가 부족하다는 것이다. 프로그램이 사용하는 메모리 양을 줄이기 위해 프로그래머는 여러 자료 구조를 사용하며, 그중 하나가 쿼드트리다.

이 자료 구조의 내용을 설명한다. 쿼드트리를 사용하면 $0$과 $1$로 이루어진 $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$는 $2$의 거듭제곱임이 보장된다.

다음 $t$개 줄에는 각각 $t$개 문자가 주어지며, 각 문자는 $0$ 또는 $1$이다. 이 줄들이 주어진 행렬을 나타낸다.

주어진 행렬에서 원소를 최대 $k$개 바꿔 얻은 행렬을 나타내는 쿼드트리의 셀 개수로 가능한 최솟값을 출력 파일에 한 줄로 출력하라.

위 예에서는 가령 위쪽의 $1$ 두 개를 $0$으로 바꿀 수 있다. 그러면 다음 행렬이 나온다.

이 행렬을 쿼드트리로 저장하려면 셀 9개가 필요하다. 행렬 전체에 하나, $2 \times 2$ 정사각형 넷에 넷, 그중 셋은 $0$을 담고 있고, 오른쪽 아래 모서리에 해당하는 넷째는 다시 넷으로 나뉜다.