#412. 按位与

按位与

题目描述

小 R 有 nn 个非负整数 a1,a2,…,ana_1,a_2,\ldots,a_n。给定正整数 mm,要求从中恰好选出 mm 个数,使选出的这些数的二进制按位与最大。

请输出这个最大值。

输入格式

第一行两个正整数 n,mn,m。第二行 nn 个非负整数 a1,a2,…,ana_1,a_2,\ldots,a_n。

原比赛文件名为 and.in。本 Hydro 版本采用标准输入输出。

输出格式

输出一个非负整数,表示选出 mm 个数后的最大按位与值。原比赛文件名为 and.out。

输入输出样例

4 2
3 15 12 12
12
5 3
31 3 1 15 7
7

数据范围

  • 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 =1=1
77 =n=n
8∼108\sim10 =2=2
11,1211,12 2×1052\times10^5 =n−1=n-1
1313 ≤n\le n A
14,1514,15 B
16,1716,17 44 无
18,1918,19 2102^{10}
2020 2302^{30}
  • A:每个 aia_i 形如 2ki−12^{k_i}-1,其中 kik_i 为非负整数。
  • B:存在非负整数 kk,使 n=2kn=2^k,且 ai=i−1a_i=i-1。

原题题面另含文件形式的样例 3、4、5,所给文字未包含对应文件。本题数据为自行生成的民间测试数据,不是官方测试数据。