2010 월드컵 (Small)

4년 만에 다시 월드컵이 열린다. Varva는 남아프리카 공화국으로 떠나 결선 토너먼트에 맞춰 도착한다.

결선 토너먼트에서는 모든 경기에 승자가 있다. 이긴 팀은 다음 라운드로 올라가고 진 팀은 탈락한다. 이 단계에는 $2^P$개의 팀이 참가하며, 각 팀은 0부터 $2^P - 1$까지의 정수로 구분한다. 결선 토너먼트는 $P$개의 라운드로 이루어지고, 각 라운드에서 남아 있는 모든 팀은 정확히 한 경기씩 치른다. 대진과 경기 순서는 남아 있는 팀 가운데 번호가 가장 작은 두 팀을 차례로 짝지어 정한다. 한 라운드의 경기가 모두 끝나면 다음 라운드가 시작된다.

Varva는 팀마다 애정이 달라서, 팀 i가 치르는 경기 중 최대 M[i]개까지만 놓칠 생각이 있다.

Varva는 경기 결과가 어떻게 나오든 이 조건이 반드시 지켜지도록 표를 사야 한다. 그 밖에는 돈을 최대한 적게 쓰고 싶다. 표를 사는 데 필요한 최소 금액을 구하라.

표는 대회가 시작하기 전에 미리 사야 하고, 각 경기의 표 가격은 미리 알려져 있다. 경기마다 가격이 다를 수 있다.

예시

위 그림은 대진표와 표 가격의 예다. 1라운드 경기 (0, 1), (2, 3), (4, 5), (6, 7)의 가격은 각각 100, 150, 50, 90이고, 2라운드 두 경기의 가격은 500과 400, 결승전 가격은 800이다. M = {1, 2, 3, 2, 1, 0, 1, 3}이라고 하자. 팀 5의 경기는 하나도 놓칠 수 없으므로 팀 5가 치를 수 있는 모든 경기의 표를 50, 400, 800에 사야 한다. 이 표만으로 팀 0을 뺀 나머지 팀의 조건은 모두 지켜진다. 팀 0은 1라운드 경기 표를 100에 더 사는 것이 가장 싸고, 합계는 1350이다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 정수 $P$가 주어진다. 다음 줄에는 $2^P$개의 정수 M[0], ..., 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$ 이하의 정수이다.
• 각 표 가격은 1 이상 1000000 이하의 정수이다.

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