카드의 집

마르첼은 올해 생일에 아주 특별한 카드 한 벌을 선물로 받았다. 이 카드는 게임용이 아니라 카드로 집(탑)을 쌓기 위한 것이다. 선물을 풀자마자 마르첼은 커다란 탑을 하나 세웠다. 세우는 방법은 이렇다. 먼저 카드 두 장을 서로 마주 기대어 세워 하나의 꼭짓점을 만들고, 그렇게 만들어진 꼭짓점들 위에 다시 카드를 두 장씩 마주 기대어 세우며 위층을 차례로 쌓아 올린다. 맨 아래층을 제외한 모든 층에서 꼭짓점의 개수가 항상 짝수였기 때문에, 언제나 바로 위층을 올바르게 쌓을 수 있었다.

각 카드에는 고유한 값이 매겨져 있다. 마르첼은 탑을 더 신중하게 설계하지 못해 값비싼 카드를 너무 많이 써 버린 것을 후회하고 있다. 각 카드의 값을 알 때, 그는 탑에서 카드를 최대 $k$장까지 빼내어 빼낸 카드들의 값의 합을 최대로 만들고 싶다. 물론 그 과정에서 카드의 집이 무너져서는 안 된다.

카드를 빼낸 뒤에도 집이 안정적으로 서 있으려면 다음 두 규칙을 지켜야 한다. 첫째, 서로 마주 기대어 지탱하는 짝(쌍)을 이루는 두 카드는 항상 함께 빼내야 하며, 한 장만 따로 빼낼 수는 없다. 둘째, 어떤 카드를 빼내려면 그 카드 위에 놓여 직접 또는 간접적으로 그 카드에 기대고 있는 카드들을 모두 먼저 빼내야 한다.

첫째 줄에 두 정수 $n$과 $k$가 주어진다 ($2 \le n \le 17$, $2 \le k \le 40$). $n$은 카드 탑의 층 수이고, $k$는 마르첼이 빼낼 수 있는 카드의 최대 개수이다. 카드는 짝을 이루어 쌍으로만 빼낼 수 있으므로 $k$는 항상 짝수이다.

이어지는 $n$개의 줄은 탑의 각 층을 맨 위층부터 맨 아래층까지 차례로 나타낸다. 위에서 $i$번째 층 ($1 \le i \le n$)을 나타내는 줄에는 $2^i$개의 정수 $a_{i,1}, a_{i,2}, \dots, a_{i,2^i}$가 왼쪽부터 오른쪽 순서로 주어지며, 이는 그 층에 놓인 카드들의 값이다 ($-1\,000\,000 \le a_{i,j} \le 1\,000\,000$).

탑이 무너지지 않도록 카드를 최대 $k$장 빼낼 때 마르첼이 되찾을 수 있는 카드 값의 최대 합을 정수 하나로 출력한다.

그림에서 점선으로 표시된 카드들이 마르첼이 빼내야 하는 카드이다. 그 값은 각각 $1$, $-3$, $2$, $1$, $-1$, $5$이며, 따라서 값의 합은 $5$이다.