题目描述

長さ $N$ の非負整数列 $A=(A_1,A_2,\dots,A_N)$ が与えられます。あなたは以下の操作を $M$ 回以下行うことができます。($1$ 回も行わなくてもよいです。)

• $1\ \le\ i\ \le\ N$ を満たす整数 $i$ を選び、$A_i$ を $1$ 増やす。

その後、$A$ の中から $K$ 要素を選びます。

選んだ $K$ 要素のビット単位 $\mathrm{AND}$ の最大値を求めてください。

ビット単位 $\mathrm{AND}$ 演算とは 整数 $A,\ B$ のビット単位 $\mathrm{AND}$、$A\ \mathrm{AND}\ B$ は以下のように定義されます。

• $A\ \mathrm{AND}\ B$ を二進表記した際の $2^k$ ($k\ \geq\ 0$) の位の数は、$A,\ B$ を二進表記した際の $2^k$ の位の数のうち両方が $1$ であれば $1$、そうでなければ $0$ である。

例えば、$3\ \mathrm{AND}\ 5\ =\ 1$ となります (二進表記すると: $011\ \mathrm{AND}\ 101\ =\ 001$)。
一般に $k$ 個の整数 $p_1,\ p_2,\ p_3,\ \dots,\ p_k$ のビット単位 $\mathrm{AND}$ は $ (\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$ の順番によらないことが証明できます。 ​

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

答えを出力せよ。

题目大意

给定一个非负整数序列，可以将一些整数变大，总量不超过 $M$ ，从中选 $K$ 个整数，求这 $K$ 个整数的最大位与运算值。

translate by @wsfxk (uid=376161)

4 8 2
1 2 4 8

10

5 345 3
111 192 421 390 229

461

提示

制約

• $1\ \le\ K\ \le\ N\ \le\ 2\ \times\ 10^5$
• $0\ \le\ M\ <\ 2^{30}$
• $0\ \le\ A_i\ <\ 2^{30}$
• 入力は全て整数である。

Sample Explanation 1

以下のような手順を踏むことで 選んだ $2$ 要素の $\mathrm{AND}$ として $10$ を達成できます。 - $A_3$ を選ぶ操作を $6$ 回行う。$A_3\ =\ 10$ となる。 - $A_4$ を選ぶ操作を $2$ 回行う。$A_4\ =\ 10$ となる。 - $A_3,A_4$ を選ぶ。$2$ 要素の $\mathrm{AND}$ は $10$ である。 選んだ $2$ 要素の $\mathrm{AND}$ を $11$ 以上にすることはできないので、解は $10$ です。