分数: 600 点
问题陈述
我们有 N 宝石。的色彩和美感 i-第宝石是
分别为 D_i 和 V_i。
这里,每颗宝石的颜色是其中之一 1, 2, \ldots, C,并且每种颜色至少有一颗宝石。
出 N 宝石,我们会选择 C 具有不同的颜色,并用它们制作项链。 (顺序并不重要。) 项链的美丽就在于按位 所选宝石的 \rm XOR 。
在所有可能的项链制作方法中,找出用以下方法制作的项链的美丽之处: K- 最伟大的美丽。 (如果有多种方式具有相同的美感,我们将全部计算在内。)
什么是按位 \rm XOR?
按位 \rm XOR 整数 A 和 B, A \oplus B,定义如下:
- 当 A \oplus B 以基数 2 书写,即 2^k的地点 (k \geq 0) 是 1 如果 A or B,但不是两者都有 1 在 2^k的地点,以及 0 否则。
约束
- 1 \leq C \leq N \leq 70
- 1 \leq D_i \leq C
- 0 \leq V_i < 2^{60}
- 1 \leq K \leq 10^{18}
- 至少有 K 制作项链的方法。
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N C K D_1 V_1 \vdots D_N V_N
输出
打印答案。
示例输入 1
4 2 3 2 4 2 6 1 2 1 3
示例输出 1
5
项链的制作方法有四种,如下。
- 选择 1-st 和 3-rd 宝石制作一条美丽的项链 4\ {\rm XOR}\ 2 =6.
- 选择 1-st 和 4- 宝石制作一条美丽的项链 4\ {\rm XOR}\ 3 =7.
- 选择 2-nd 和 3-rd 宝石制作一条美丽的项链 6\ {\rm XOR}\ 2 =4.
- 选择 2-nd 和 4- 宝石制作一条美丽的项链 6\ {\rm XOR}\ 3 =5.
因此,项链 3-rd 最大的美丽有以下的美丽 5.
示例输入 2
3 1 2 1 0 1 0 1 0
示例输出 2
0
项链的制作方法有3种,这三种方法都会带来美丽的效果 0.
示例输入 3
10 3 11 1 414213562373095048 1 732050807568877293 2 236067977499789696 2 449489742783178098 2 645751311064590590 2 828427124746190097 3 162277660168379331 3 316624790355399849 3 464101615137754587 3 605551275463989293
示例输出 3
766842905529259824