题目描述

给定一个长度为 $N$ 的非负整数序列 $A=(A_1,A_2,\dots,A_N)$。你可以进行不超过 $M$ 次如下操作（也可以一次都不进行）：

• 选择一个满足 $1 \leq i \leq N$ 的整数 $i$，将 $A_i$ 增加 $1$。

操作结束后，从 $A$ 中选择 $K$ 个元素。

请你求出所选 $K$ 个元素的按位与（bitwise AND）的最大值。

按位与（bitwise AND）运算的定义如下：
对于整数 $A,B$，$A$ 和 $B$ 的按位与 $A \mathrm{AND} B$，其二进制表示中每一位 $2^k$（$k \geq 0$）的数值为 $A$ 和 $B$ 的该位都为 $1$ 时为 $1$，否则为 $0$。

例如，$3 \mathrm{AND} 5 = 1$（二进制为 $011 \mathrm{AND} 101 = 001$）。
一般地，$k$ 个整数 $p_1,p_2,\dots,p_k$ 的按位与定义为 $(\dots((p\_1 \mathrm{AND} p\_2) \mathrm{AND} p\_3)\dots\mathrm{AND} p\_k)$，并且可以证明与顺序无关。

输入格式

输入从标准输入中给出，格式如下：

$N$ $M$ $K$ $A_1$ $A_2$ $\dots$ $A_N$

输出格式

输出答案。

样例 1

输入

4 8 2
1 2 4 8

输出

10

样例 2

输入

5 345 3
111 192 421 390 229

输出

461

说明/提示

限制条件

• $1 \leq K \leq N \leq 2 \times 10^5$
• $0 \leq M < 2^{30}$
• $0 \leq A_i < 2^{30}$
• 输入均为整数。

样例解释 1

可以按如下步骤使得选出的 $2$ 个元素的按位与达到 $10$：

• 对 $A_3$ 进行 $6$ 次操作，使 $A_3=10$。
• 对 $A_4$ 进行 $2$ 次操作，使 $A_4=10$。
• 选择 $A_3,A_4$，这两个元素的按位与为 $10$。

无法使选出的 $2$ 个元素的按位与达到 $11$ 或更大，因此答案为 $10$。

由 ChatGPT 4.1 翻译