luogu#P6824. 「EZEC-4」可乐

「EZEC-4」可乐

题目背景

很久以前,有一个 pigstd,非常迷恋美味的可乐。为了得到美味的可乐,他几乎用尽了所有的钱,他甚至对自己的 npy 也漠不关心其实是因为他没有npy,更不爱好看戏。除非买了新可乐,才会坐上马车出门炫耀一番。每一天,每个钟头他都要喝上一瓶新可乐。

pigstd 最近又买了许多箱新可乐——当然,这些可乐只有聪明的人才能喝到。

题目描述

pigstd 现在有 nn 箱可乐,第 ii 箱可乐上标着一个正整数 aia_{i}

若 pigstd 的聪明值为一个非负整数 xx,对于第 ii 箱可乐,如果 (aix)k(a_{i} \oplus x )\le k,那么 pigstd 就能喝到这箱可乐。

现在 pigstd 告诉了你 kk 与序列 aa,你可以决定 pigstd 的聪明值 xx,使得他能喝到的可乐的箱数最大。求出这个最大值。

输入格式

第一行两个由空格分隔开的整数 n,kn,k

接下来 nn 行,每行一个整数 aia_i,表示第 ii 箱可乐上标的数。

输出格式

一行一个正整数,表示 pigstd 最多能喝到的可乐的箱数。

3 5
2
3
4
3
4 625
879
480
671
853

4

提示

提示

pigstd 的聪明值 xx 可以为 00

样例解释

样例 1 解释:容易构造当 x=0x = 0 时,可以喝到所有可乐。

样例 2 解释:容易构造 x=913x = 913,可以喝到所有可乐。

样例解释未必是唯一的方法。

数据范围

本题采用捆绑测试。

  • Subtask 1(29 points):1n,k,ai10001 \le n,k,a_{i} \le 1000

  • Subtask 2(1 points):aika_{i} \le k

  • Subtask 3(70 points):无特殊限制。

对于所有数据,保证 1n,k,ai1061 \le n,k,a_{i} \le 10^6

\oplus 代表异或,如果您不知道什么是异或,请单击这里