← Home
write a go solution for Description:
There are currently n hot topics numbered from 0 to n-1 at your local bridge club and 2^n players numbered from 0 to 2^n-1. Each player holds a different set of views on those n topics, more specifically, the i-th player holds a positive view on the j-th topic if i&2^j>0, and a negative view otherwise. Here & denotes the bitwise AND operation.

You are going to organize a bridge tournament capable of accommodating at most k pairs of players (bridge is played in teams of two people). You can select teams arbitrarily while each player is in at most one team, but there is one catch: two players cannot be in the same pair if they disagree on 2 or more of those n topics, as they would argue too much during the play.

You know that the i-th player will pay you a_i dollars if they play in this tournament. Compute the maximum amount of money that you can earn if you pair the players in your club optimally.

Input Format:
The first line contains two integers n, k (1<=n<=20, 1<=k<=200) — the number of hot topics and the number of pairs of players that your tournament can accommodate.

The second line contains 2^n integers a_0,a_1,...,a_2^n-1 (0<=a_i<=10^6) — the amounts of money that the players will pay to play in the tournament.

Output Format:
Print one integer: the maximum amount of money that you can earn if you pair the players in your club optimally under the above conditions.

Note:
In the first example, the best we can do is to pair together the 0-th player and the 2-nd player resulting in earnings of 8+5=13 dollars. Although pairing the 0-th player with the 5-th player would give us 8+10=18 dollars, we cannot do this because those two players disagree on 2 of the 3 hot topics.

In the second example, we can pair the 0-th player with the 1-st player and pair the 2-nd player with the 3-rd player resulting in earnings of 7+4+5+7=23 dollars.. Output only the code with no comments, explanation, or additional text.