← 返回题目列表

Codeforces · 981/D

D. 书架

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

Keks先生是Byteland的典型白领。

他的办公室里有一个书架,上面放着一些书,每本书都有一个整数正的价格。

Keks 先生将书架的价值定义为书架上书籍价格的总和。

Keks 先生奇迹般地升职了,现在他正在搬进新办公室。

他了解到,在新办公室里,他将不再有一个书架,而是恰好有 $$$k$$$ 个书架。他认为 $$$k$$$ 架子的美妙之处在于所有架子的值的按位与。

他还决定不会花时间重新排序书籍,因此他会将几本书放在第一个书架上,将几本书放在下一个书架上,依此类推。当然,他会在每个书架上至少放置一本书。这样他就会把他所有的书都放在$$$k$$$架子上,这样架子的美观就尽可能大。计算这个最大可能的美丽。

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \leq k \leq n \leq 50$$$) — 新办公室的书籍数量和书架数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots a_n$$$, ($$$0 < a_i < 2^{50}$$$) — 书籍的价格(按旧书架上的顺序排列)。

输出

打印新办公室中 $$$k$$$ 架子的最大可能的美丽。

示例

输入 #1

10 4
9 14 28 1 7 13 15 29 2 31

输出 #1

24

输入 #2

7 3
3 14 15 92 65 35 89

输出 #2

64

注意

在第一个示例中,您可以按如下方式拆分书籍:

$$$$$$(9 + 14 + 28 + 1 + 7) \& (13 + 15) \& (29 + 2) \& (31) = 24.$$$$$$

在第二个示例中,您可以按如下方式拆分书籍:

$$$$$$(3 + 14 + 15 + 92) \& (65) \& (35 + 89) = 64.$$$$$$