World Cup 2010 (Small)

Four years on, the World Cup is here again, and Varva is flying to South Africa in time for the knockout stage.

Every match of the knockout stage has a winner. The winning team goes on to the next round and the losing team is out of the tournament. $2^P$ teams play in this stage, identified by the integers from 0 to $2^P - 1$. The knockout stage runs for $P$ rounds, and in each round every remaining team plays exactly one match. The pairings and the order of the matches come from repeatedly taking the two remaining teams with the smallest identifiers and putting them in one match. Once every match of a round is over, the next round starts.

Varva likes some teams more than others, so for each team i he is willing to miss at most M[i] of the matches that team plays.

Varva has to buy tickets that keep every one of those limits, no matter how the matches turn out. Beyond that he wants to spend as little money 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 known. Prices may differ from match to match.

Example

The figure above shows a bracket together with its ticket prices. The first round matches (0, 1), (2, 3), (4, 5) and (6, 7) cost 100, 150, 50 and 90. The two second round matches cost 500 and 400, and the final costs 800. Suppose M = {1, 2, 3, 2, 1, 0, 1, 3}. No match of team 5 may be missed, so Varva buys tickets for every match team 5 can play in, spending 50, 400 and 800. Those tickets already satisfy every team except team 0. The cheapest fix for team 0 is the ticket for its first round match, another 100, for a total of 1350.

The first line contains the number of test cases $T$. Each test case starts with a line holding one integer $P$. The next line holds $2^P$ integers, the limits M[0], ..., M[2^P - 1].

The following $P$ lines hold the ticket prices of all matches. The first of those lines holds $2^{P-1}$ integers, the prices of the first round matches. The second line holds $2^{P-2}$ integers, the prices of the second round matches, and so on. The last of the $P$ lines holds one integer, the ticket price of the final. 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.
• Each ticket price is an integer between 1 and 1000000, 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.