시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 28 9 7 28.000%

문제

과학자들은 화성에서 특이한 박테리아를 발견했고, 열심히 조사하고 있다. 그들은 박테리아의 개수가 2의 제곱수인 것을 알아챘다. 그것은 이들이 1개의 박테리아에서 시작되고, 각 박테리아는 매 세대 2개의 박테리아로 분열하기 때문이다(원래의 박테리아는 없어지는 꼴이다).

즉, 1세대는 하나의 박테리아, 2세대는 첫 세대의 박테리아가 둘로 나누어진 두 박테리아, 3세대는 또 그것이 나누어진 네 개의 박테리아, 4세대는 여덟 개, 이런 식으로 K+1세대에는 2k개의 박테리아가 있는 것을 알게 되었다.

과학자들은 그들이 찾아낸 박테리아를 1부터 2K까지 다음과 같이 번호 붙였다.

  • 이전의 K세대의 박테리아들의 후손은: {1, 2}, {3, 4}, {5, 6}, ..., {2K-1, 2K}
  • 더욱 전의 (K-1)세대의 박테리아들의 후손은: {1, 2, 3, 4}, {5, 6, 7, 8}, ..., {2K-3, 2K-2, 2K-1, 2K}
  • 훨씬 더욱 전의 (K-2)세대의 박테리아들의 후손은: {1, 2, 3, 4, 5, 6, 7, 8}, ..., {2K-7, 2K-6, 2K-5, 2K-4, 2K-3, 2K-2, 2K-1, 2K}
  • ...
  • 2세대의 두 박테리아의 후손은: {1, 2, ..., 2K-1}와 {2K-1 + 1, 2K-1 + 2, ..., 2K}

중괄호는 이들이 한 박테리아의 후손들이라는 뜻이다. 즉 어떤 조상 박테리아의 후손도 연속된 번호를 가지고 있도록 번호붙여졌다.

이 때 박테리아의 순서를 바꾸더라도 여전히 위의 규칙을 만족하게 할 수 있는데, 과학자들은 그런 순서들 중 '순열의 길이'를 최소화하는 규칙을 찾으려 한다. '순열의 길이'는 이웃한 박테리아 사이의 거리를 모두 합한 것으로 정의된다.

정확히는, 모든 두 박테리아 사이에는 반발력이 존재하는데, 이 반발력은 수치로 나타내어진다. 두 박테리아 사이의 반발력은 두 박테리아가 서로 이웃해 있을 때 떨어져야 하는 최소 길이이다(두 박테리아가 이웃하지 않는다면 반발력은 아무 효과도 미치지 않는다). 모든 박테리아 쌍들의 반발력이 주어질 때, 이들을 앞서 말한 규칙을 지키면서 나열할 수 있는 최소의 길이를 구하시오.

입력

입력의 첫 줄에는 문제에서 언급한 양수 K가 주어진다(1 ≤ K ≤ 9).

그 후의 2K개의 줄에는 [0, 106] 범위에 있는 2K개의 자연수가 주어진다. 2K × 2K개의 숫자는 박테리아 쌍들 사이의 반발력을 뜻한다: 여기서 (m, n)에 있는 숫자는 박테리아 m과 n 사이의 반발력을 뜻한다. (m, n)과 (n, m)에는 같은 숫자가 들어가고, m = n일 때는 0이다.

출력

조건을 만족하면서 박테리아를 나열하는 최소의 길이만을 출력하라.

예제 입력

2
0 7 2 1
7 0 4 3
2 4 0 5
1 3 5 0

예제 출력

13

힌트