#P2226. 按位与

按位与

本题需要文件读写

文件 IO 为:输入文件 and.in,输出文件 and.out。请使用上述文件名读入和输出。

问题描述

小 R 有 nn 个非负整数 a1,a2,…,ana_1,a_2,\ldots,a_n。

小 X 给出一个正整数 mm,要求从这 nn 个数中选出恰好 mm 个,使选出的数的二进制按位与的值最大。

请输出这个最大值。

输入格式

从文件 and.in 中读入数据。

第一行输入两个正整数 n,mn,m。

第二行输入 nn 个非负整数 a1,a2,…,ana_1,a_2,\ldots,a_n。

输出格式

输出到文件 and.out。

输出一行一个非负整数,表示恰好选出 mm 个数时,按位与的最大值。

样例输入 1

4 2
3 15 12 12

样例输出 1

12

样例输入 2

5 3
31 3 1 15 7

样例输出 2

7

说明

样例 1 中,选出 1515 和 1212,或者选出两个 1212,按位与都等于 1212。

样例 2 中,可以选出 31,15,731,15,7,按位与等于 77。

评测数据规模

对于所有数据,保证:

  • 1≤m≤n≤2×1051\le m\le n\le2\times10^5;
  • 0≤ai<2300\le a_i<2^{30};
  • 所有输入数值均为整数。
测试点编号 n≤n\le mm max⁡ai<\max a_i< 特殊性质
1∼51\sim5 2020 ≤n\le n 2202^{20} 无
66 20002000 11
77 nn
8∼108\sim10 22
11,1211,12 2×1052\times10^5 n−1n-1
1313 ≤n\le n A
14,1514,15 B
16,1716,17 44 无
18,1918,19 2102^{10}
2020 2302^{30}

特殊性质 A:对于每个 ii,存在非负整数 kik_i,使得 ai=2ki−1a_i=2^{k_i}-1。

特殊性质 B:存在非负整数 kk,使得 n=2kn=2^k,且对所有 ii 均有 ai=i−1a_i=i-1。

本题共 2020 个独立测试点,每点 55 分。