← 返回题目列表

Codeforces · 1572/D

D. 桥牌俱乐部

中文机器翻译题面 查看原题

目前,您当地的桥牌俱乐部有 $$$n$$$ 热门话题,编号从 $$$0$$$ 到 $$$n-1$$$,$$$2^n$$$ 玩家编号从 $$$0$$$ 到 $$$2^n-1$$$。每个玩家对这些 $$$n$$$ 主题持有不同的看法,更具体地说,如果 $$$i\ \&\ 2^j > 0$$$,则第 $$$i$$$ 个玩家对第 $$$j$$$ 个主题持有积极看法,否则持有消极看法。这里$$$\&$$$表示按位与运算。

您将组织一场桥牌锦标赛,最多可容纳 $$$k$$$ 对玩家(桥牌以两人一组进行)。您可以任意选择队伍,每个玩家最多属于一个队伍,但有一个问题:如果两名玩家在 $$$2$$$ 或更多 $$$n$$$ 主题上存在分歧,则不能属于同一对,因为他们会在比赛中争论太多。

您知道第 $$$i$$$ 位玩家如果参加本次锦标赛,将向您支付 $$$a_i$$$ 美元。计算如果您将俱乐部中的球员进行最佳配对,您可以赚取的最高金额。

输入

第一行包含两个整数 $$$n$$$, $$$k$$$ ($$$1 \le n \le 20$$$, $$$1 \le k \le 200$$$) — 热门话题的数量和你的锦标赛可以容纳的玩家对的数量。

第二行包含 $$$2^n$$$ 整数 $$$a_0, a_1, \dots, a_{2^n-1}$$$ ($$$0 \le a_i \le 10^6$$$) — 玩家为参加锦标赛而支付的金额。

输出

打印一个整数:如果您俱乐部中的球员在上述条件下进行最佳配对,您可以获得的最大金额。

示例

输入 #1

3 1
8 3 5 7 1 10 3 2

输出 #1

13

输入 #2

2 3
7 4 5 7

输出 #2

23

输入 #3

3 2
1 9 1 5 7 8 1 1

输出 #3

29

注意

在第一个示例中,我们能做的最好的事情就是将第 $$$0$$$ 玩家与第 $$$2$$$ 玩家配对,从而获得 $$$8 + 5 = 13$$$ 美元的收入。尽管将第 $$$0$$$ 玩家与第 $$$5$$$ 玩家配对会给我们 $$$8 + 10 = 18$$$ 美元,但我们不能这样做,因为这两个玩家在 $$$3$$$ 热门话题上的 $$$2$$$ 存在分歧。

在第二个示例中,我们可以将第 $$$0$$$ 玩家与第 $$$1$$$ 玩家配对,并将第 $$$2$$$ 玩家与第 $$$3$$$ 玩家配对,从而获得 $$$7 + 4 + 5 + 7 = 23$$$ 美元的收入。