월드컵 2010

4년이 지나 다시 World Cup 때가 되었고, Varva는 대회의 두 번째 단계를 제때 관람하기 위해 South Africa로 향하고 있다.

두 번째 단계(토너먼트 단계라고도 한다)에서는 각 경기에 항상 승자가 있으며, 승리한 팀은 다음 라운드로 진출하고 패배한 팀은 대회에서 탈락한다. 이 단계에는 $2^{P}$개의 팀이 참가하며, 0부터 $2^{P}$ - 1까지의 정수로 식별된다. 토너먼트 단계는 P개의 라운드로 구성된다. 각 라운드에서 남아 있는 각 팀은 정확히 한 경기를 치른다. 정확한 대진과 경기 순서는 남아 있는 팀 중 식별자가 가장 작은 두 팀을 차례로 선택하여 한 경기의 대진으로 묶는 방식으로 결정된다. 한 라운드의 모든 경기가 끝나면 다음 라운드가 시작된다.

어떤 경기를 볼지 결정하기 위해, Varva는 특정 팀을 얼마나 좋아하는지에 따라 제약 조건 목록을 만들었다. 구체적으로 각 팀 i에 대해, 그는 그 팀이 대회에서 치르는 경기 중 최대 M[i]개까지 관람하지 않아도 괜찮다.

Varva는 경기 결과가 어떻게 되든 자신의 선호 조건이 충족되도록 보장하는 티켓 집합을 구매해야 한다. 그 외에는 가능한 한 적은 돈을 쓰고 싶을 뿐이다. 여러분의 목표는 그가 티켓에 지출해야 하는 최소 금액을 구하는 것이다.

경기 티켓은 대회가 시작되기 전에 미리 구매해야 하며, 각 경기의 티켓 가격은 알려져 있다. 작은 입력에서는 모든 경기의 티켓 가격이 같지만, 큰 입력에서는 서로 다를 수 있음에 유의한다.

예제

티켓 가격이 표시된 대회 일정의 예가 위 그림에 주어진다. 제약 조건이 배열 M = {1, 2, 3, 2, 1, 0, 1, 3}로 주어진다고 하자. 최적 전략은 다음과 같다. 팀 5의 경기는 하나도 놓칠 수 없으므로, 팀 5이 치를 가능성이 있는 모든 경기의 티켓을 구매하는 데 50, 400, 그리고 800를 지출해야 한다. 이제 팀 0을 제외한 다른 팀들의 제약 조건도 이 티켓들로 충족된다. 이를 해결하는 최선의 방법은 팀 0의 첫 라운드 경기 티켓을 구매하여 100를 추가로 지출하는 것이며, 총액은 1350가 된다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 1 ≤ T ≤ 50 1 ≤ P ≤ 10 M의 각 원소는 0 이상 P 이하인 정수이다.

작은 데이터 세트(테스트 세트 1 - 공개)

모든 가격은 1로 같다.

큰 데이터 세트(테스트 세트 2 - 비공개)

모든 가격은 0 이상 100000 이하인 정수이다.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 케이스는 하나의 정수 P가 있는 줄로 시작한다. 다음 줄에는 제약 조건 M[0], ..., M[2^{P}-1]를 나타내는 $2^{P}$개의 정수가 주어진다.

이어지는 P개 줄의 블록에는 모든 경기의 티켓 가격이 주어진다. 블록의 첫 줄에는 첫 라운드 경기의 티켓 가격인 2^{P-1}개의 정수가 주어지고, 블록의 두 번째 줄에는 두 번째 라운드 경기의 티켓 가격인 2^{P-2}개의 정수가 주어지는 식이다. P개 줄 중 마지막 줄에는 World Cup의 결승전 티켓 가격인 하나의 정수가 주어진다. 가격은 경기가 치러지는 순서대로 나열된다.

각 테스트 케이스마다 "Case #x: y"를 포함하는 한 줄을 출력한다. 여기서 x는 케이스 번호(1부터 시작)이고, y는 위에서 설명한 대로 Varva가 티켓에 지출해야 하는 최소 금액이다.