← 返回题目列表

AtCoder · dwacon5th_prelims_b

B. 求和与子数组

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

分数: 400 点

问题陈述

有一天,Dwango Co., Ltd. 的员工 Niwango-kun 发现了一个整数序列 (a_1, ..., a_N) 长度 N。 他对序列的性质感兴趣 a.

对于非空连续子序列 a_l, ..., a_r (1 \leq l \leq r \leq N) 序列的 a,其 美女 定义为 a_l + ... + a_r。 Niwango-kun 想知道按位与的最大可能值 K 所有之间的非空连续子序列 N(N+1)/2 非空连续子序列。 (子序列可以共享元素。)

找出他的最大可能值。

约束

  • 2 \leq N \leq 1000
  • 1 \leq a_i \leq 10^9
  • 1 \leq K \leq N(N+1)/2
  • 输入中给出的所有数字均为整数

输入

输入由标准输入按以下格式给出:

N K
a_1 a_2 ... a_N

输出

打印答案。


示例输入 1

4 2
2 5 2 5

示例输出 1

12

有 10 的非空连续子序列 a。让我们一一列举:

  • 从第一个元素开始的连续子序列: \{2\}, \{2, 5\}, \{2, 5, 2\}, \{2, 5, 2, 5\}
  • 从第二个元素开始的连续子序列: \{5\}, \{5, 2\}, \{5, 2, 5\}
  • 从第三个元素开始的连续子序列: \{2\}, \{2, 5\}
  • 从第四个元素开始的连续子序列: \{5\}

(注意,即使子序列的元素相等,具有不同起始索引的子序列也被认为是不同的。)

两个不同连续子序列的美女的最大可能按位与为 12。 这可以通过选择来实现 \{5, 2, 5\} (有美 12)和 \{2, 5, 2, 5\} (有美 14).


示例输入 2

8 4
9 1 8 2 7 5 6 4

示例输出 2

32