/ 
Time Limit: 5 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
長さ 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 である。
一般に 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 の順番によらないことが証明できます。
制約
- 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
以下のような手順を踏むことで 選んだ 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 です。
入力例 2
5 345 3 111 192 421 390 229
出力例 2
461
Score : 500 points
Problem Statement
You are given a sequence of N non-negative integers: A=(A_1,A_2,\dots,A_N). You may perform the following operation at most M times (possibly zero):
- choose an integer i such that 1 \le i \le N and add 1 to A_i.
Then, you will choose K of the elements of A.
Find the maximum possible value of the bitwise \mathrm{AND} of the elements you choose.
What is bitwise {\rm AND}?
The bitwise {\rm AND} of non-negative integers A and B, A\ \mathrm{AND}\ B, is defined as follows:
- When A\ {\rm AND}\ B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if both of the digits in that place of A and B are 1, and 0 otherwise.
Generally, the bitwise {\rm AND} of k non-negative integers p_1, p_2, p_3, \dots, p_k is defined as (\dots ((p_1\ \mathrm{AND}\ p_2)\ \mathrm{AND}\ p_3)\ \mathrm{AND}\ \dots\ \mathrm{AND}\ p_k). We can prove that this value does not depend on the order of p_1, p_2, p_3, \dots, p_k.
Constraints
- 1 \le K \le N \le 2 \times 10^5
- 0 \le M < 2^{30}
- 0 \le A_i < 2^{30}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M K A_1 A_2 \dots A_N
Output
Print the answer.
Sample Input 1
4 8 2 1 2 4 8
Sample Output 1
10
If you do the following, the bitwise \mathrm{AND} of the elements you choose will be 10.
- Perform the operation on A_3 six times. Now, A_3 = 10.
- Perform the operation on A_4 twice. Now, A_4 = 10.
- Choose A_3 and A_4, whose bitwise \mathrm{AND} is 10.
There is no way to choose two elements whose bitwise \mathrm{AND} is greater than 10, so the answer is 10.
Sample Input 2
5 345 3 111 192 421 390 229
Sample Output 2
461