← 返回题目列表

AtCoder · abc252_h

Ex. K号美丽项链

中文机器翻译题面 查看原题

分数: 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 否则。
例如, 3 \oplus 5 = 6。 (在基数二中: 011 \oplus 101 = 110.)

约束

  • 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