화성 박테리아 배열

과학자들은 화성에서 특이한 박테리아를 발견했다. 이 박테리아는 처음에 한 마리에서 시작하며, 한 세대가 지날 때마다 각 박테리아가 두 마리로 갈라지고 원래의 박테리아는 사라진다. 따라서 $K+1$세대에는 $2^K$마리의 박테리아가 있다.

과학자들은 마지막 세대의 박테리아를 1번부터 $2^K$번까지 번호 붙였다. 번호는 어떤 조상 박테리아의 후손들도 항상 연속된 번호 구간을 이루도록 붙어 있다. 예를 들어 $K$세대 박테리아들의 후손은 $\{1,2\}$, $\{3,4\}$, ..., $\{2^K-1,2^K\}$이고, $K-1$세대 박테리아들의 후손은 크기 4의 연속 구간들이 된다. 같은 방식으로 2세대의 두 박테리아의 후손은 각각 $\{1,2,\ldots,2^{K-1}\}$와 $\{2^{K-1}+1,\ldots,2^K\}$이다.

박테리아를 다시 나열할 때도 이 성질을 유지해야 한다. 즉, 모든 조상 박테리아에 대해 그 후손들이 새 배열에서도 하나의 연속된 구간을 이루어야 한다. 이는 계보를 나타내는 완전 이진트리의 각 내부 정점에서 왼쪽 후손 묶음과 오른쪽 후손 묶음의 순서를 독립적으로 바꾸는 것과 같다.

모든 박테리아 쌍 사이에는 반발력 값이 주어진다. 두 박테리아가 새 배열에서 이웃하면, 두 박테리아 사이의 거리는 적어도 그 반발력 값이어야 한다. 배열의 길이는 이웃한 두 박테리아 사이 거리의 합이다. 위의 계보 조건을 지키면서 만들 수 있는 배열의 최소 길이를 구하시오.

첫 줄에 양의 정수 $K$가 주어진다. $(1 \le K \le 9)$

이후 $2^K$개의 줄에 걸쳐 반발력 행렬이 주어진다. 각 줄에는 $2^K$개의 정수가 있으며, 모든 값은 $0$ 이상 $10^6$ 이하이다. $m$번째 줄의 $n$번째 수는 박테리아 $m$과 박테리아 $n$ 사이의 반발력이다. 행렬은 대칭이고, 같은 박테리아끼리의 반발력은 $0$이다.

조건을 만족하는 배열의 최소 길이를 출력한다.