World Cup 2010 (Large)

Four years have passed, the World Cup is on again, and Varva is travelling to South Africa in time for the second stage of the tournament.

The second stage, also called the knockout stage, gives every match a winner. The winning team goes on to the next round and the losing team is out of the tournament. There are $2^P$ teams in this stage, identified by the integers $0$ through $2^P - 1$. The knockout stage has $P$ rounds, and in each round every remaining team plays exactly one match. The pairs and the order of the matches in a round come from repeatedly taking the two remaining teams with the lowest identifiers and pairing them. In other words, line the remaining teams up by identifier, pair them off from the front, and play the matches in that order. Once all matches of a round are finished, the next round starts.

The figure shows a bracket for $P = 3$ together with the ticket price of every match.

Varva likes some teams more than others, so he has written his conditions down. For team $i$ he is willing to miss at most $M[i]$ matches that the team plays in the tournament.

He has to buy tickets so that all of these conditions hold no matter how the matches turn out, and he wants to spend as little as possible. Find the minimum amount of money he needs to spend on tickets.

Tickets are bought before the tournament starts, and the ticket price of every match is already known. Prices may differ from match to match.

The first line contains the number of test cases, $T$. $T$ test cases follow. Each test case starts with a line containing a single integer $P$. The next line contains $2^P$ integers $M[0], M[1], \ldots, M[2^P - 1]$.

The following $P$ lines contain the ticket prices of all matches. The first of those lines contains $2^{P-1}$ prices for the first round matches, the second line contains $2^{P-2}$ prices for the second round matches, and so on, until the last line contains a single price for the final. Within each line the prices are listed in the order the matches are played.

Limits

• $1 \le T \le 50$
• $1 \le P \le 10$
• Each element of $M$ is an integer between $0$ and $P$, inclusive.
• Every price is an integer between $0$ and $100000$, inclusive.

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from $1$ and $y$ is the minimum amount of money Varva needs to spend on tickets.