월드컵 2010 (라지)

4년이 지나 다시 월드컵이 열리고, 바르바는 토너먼트 2라운드를 보려고 남아프리카 공화국으로 떠난다.

2라운드는 녹아웃 스테이지라고도 부르며, 모든 경기에는 반드시 승자가 있다. 이긴 팀은 다음 라운드로 올라가고 진 팀은 대회에서 탈락한다. 이 단계에 참가하는 팀은 $2^P$개이고, 각 팀은 $0$부터 $2^P - 1$까지의 정수로 구분한다. 녹아웃 스테이지는 $P$개의 라운드로 이루어지며, 각 라운드마다 남아 있는 모든 팀이 정확히 한 경기씩 치른다. 한 라운드의 대진과 경기 순서는 남아 있는 팀 중에서 번호가 가장 작은 두 팀을 뽑아 맞붙이는 일을 반복해서 정한다. 즉 남은 팀을 번호 순으로 세워 앞에서부터 두 팀씩 짝지으며, 경기도 그 순서대로 열린다. 한 라운드의 경기가 모두 끝나면 다음 라운드가 시작된다.

그림은 $P = 3$인 대진표와 각 경기의 티켓 가격을 보여 준다.

바르바는 팀마다 애정이 다르므로 조건을 미리 정리해 두었다. 팀 $i$가 대회에서 치르는 경기 중 최대 $M[i]$경기까지만 놓칠 생각이다.

경기 결과가 어떻게 나오더라도 이 조건이 모두 지켜지도록 티켓을 사야 하고, 그러면서 돈은 되도록 적게 쓰고 싶다. 티켓을 사는 데 필요한 최소 금액을 구하여라.

티켓은 대회가 시작하기 전에 미리 사야 하며, 각 경기의 티켓 가격은 이미 알려져 있다. 경기에 따라 가격이 서로 다를 수 있다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫째 줄에는 정수 $P$가 주어진다. 다음 줄에는 $2^P$개의 정수 $M[0], M[1], \ldots, M[2^P - 1]$이 주어진다.

이어지는 $P$개의 줄에는 모든 경기의 티켓 가격이 주어진다. 첫째 줄에는 1라운드 경기의 가격 $2^{P-1}$개, 둘째 줄에는 2라운드 경기의 가격 $2^{P-2}$개가 주어지고, 같은 방식으로 이어져 마지막 줄에는 결승전의 티켓 가격 하나가 주어진다. 각 줄의 가격은 경기가 열리는 순서대로 나열된다.

제한

• $1 \le T \le 50$
• $1 \le P \le 10$
• $M$의 각 원소는 $0$ 이상 $P$ 이하의 정수이다.
• 모든 가격은 $0$ 이상 $100000$ 이하의 정수이다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 $1$부터 시작하는 테스트 케이스 번호이고, $y$는 바르바가 티켓을 사는 데 써야 하는 최소 금액이다.