← 返回题目列表

AtCoder · arc146_b

B. 加和与

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

分数: 500 点

问题陈述

给你一系列 N 非负整数: A=(A_1,A_2,\dots,A_N)。您最多可以执行以下操作 M 次(可能为零):

  • 选择一个整数 i 这样 1 \le i \le N 并添加 1 to A_i.

然后,您将选择 K 的元素 A.

找出按位的最大可能值 您选择的元素的 \mathrm{AND} 。

什么是按位 {\rm AND}?

按位 非负整数的 {\rm AND} 非负整数的 A 和 B, A\ \mathrm{AND}\ B,定义如下:

  • 当 选择 A\ {\rm AND}\ B 以基数 2 书写,其中的数字 2^k的地点 (k \geq 0) 是 1 如果该位置的两位数字 A 和 B 是 1,和 0 否则。
例如, 3\ {\rm AND}\ 5 = 1。 (在基数二中, 011\ {\rm AND}\ 101 = 001.)
一般来说,按位 {\rm AND} of k 非负整数 p_1, p_2, p_3, \dots, p_k 定义为 (\dots ((p_1\ \mathrm{AND}\ p_2)\ \mathrm{AND}\ p_3)\ \mathrm{AND}\ \dots\ \mathrm{AND}\ p_k)。我们可以证明这个值不依赖于顺序 p_1, p_2, p_3, \dots, p_k.

​

约束

  • 1 \le K \le N \le 2 \times 10^5
  • 0 \le M < 2^{30}
  • 0 \le A_i < 2^{30}
  • 输入中的所有值都是整数。

输入

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

N M K
A_1 A_2 \dots A_N

输出

打印答案。


示例输入 1

4 8 2
1 2 4 8

示例输出 1

10

如果执行以下操作,按位 您选择的元素的 \mathrm{AND} 将是 10.

  • 执行操作 A_3 六次。现在, A_3 = 10.
  • 执行操作 A_4 两次。现在, A_4 = 10.
  • 选择 A_3 和 A_4,其按位 \mathrm{AND} is 10.

无法选择两个按位排列的元素 \mathrm{AND} 大于 10,所以答案是 10.


示例输入 2

5 345 3
111 192 421 390 229

示例输出 2

461