KhanBaG’s Mafia

Time Limit: 10 Seconds    Memory Limit: 32768 KB

A knockout tournament is about to be held in the town of Mooliland. This tournament has 2^k participants to whom we give a numbering of 1, 2, ..., 2^k.

The tournament is held in k rounds. In the first round participants with numbers in the form of 2t + 1 and 2t + 2 compete and the winner goes to the next round. In the second round the winner of the match-up between 4t + 1 and 4t + 2 competes against the winner of the match-up between 4t + 3 and 4t + 4. In the same manner, in round i, the winner of the match-up between 2ⁱ t + 1 and 2ⁱ t + 2^i-1 competes the winner of the match-up between 2ⁱ t + 2^i-1 + 1 and 2ⁱ t + 2ⁱ.

The participants’ weights at the time of registration has been w₁, w₂, ..., w_2^k. KhanBaG likes the number W and has placed a bet claiming that the tournament champion’s weight is going to be W. She is willing to do anything for the champion’s weight to be equal to W. She has somehow found out that the participants who weigh less than their opponents win in the even rounds and those who weigh more than their opponent win in the odd rounds. Also, if the two opponents’ weighs are equal, the winner is chosen randomly.

There’s a clause in the tournament rules obligating the weight of the participants on competition day to be equal to their weight on registration day. KhanBaG can pay the administrators of the tournament an amount of X moollars as a bribe in order to change the clause to “the weight of the participants on competition day can differ at most X kilograms from their weight on registration day”. She wants to win the bet by changing the rule and convincing several participants to change their weight, but she can ask at most m people for weight change due to security reasons. (All tournament rounds are held on the same day and no one’s weight changes during that day.)

What is the minimum bribe she has to pay in order to win the bet?

Input

In the first line of the input comes T, the number of test cases.

The first line of each test case contains k, W, and m, which represent the the number of rounds, KhanBaG’s favorite number, and the maximum number of people she can ask to change their weights, respectively 1 ≤ m ≤ 2^k, 1 ≤ W ≤ 10⁹ and 1 ≤ k ≤ 18.

The second line of each test case contains 2^k numbers w₁, w₂, ..., w_2^k representing the participants’ weights on registration day.

Output

Print an integer representing the least amount of money KhanBaG should pay as a bribe to the administrators in order to win the bet. Print out -1 if she cannot win under any conditions.

Sample Input

2
2 15 3
50 30 20 40
2 20 1
10 10 10 10

Sample Output

25
-1

Submit

Source: 15th Iran Nationwide Internet Contest