分数: 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 否则。
一般来说,按位 {\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