第 K 美丽的项链

题目描述

我们有 $N$ 颗宝石。第 $i$ 颗宝石的颜色和美丽度分别为 $D_i$ 和 $V_i$。

这里，每颗宝石的颜色是 $1, 2, \ldots, C$ 之一，且每种颜色至少有一颗宝石。

从这 $N$ 颗宝石中，我们将选出颜色互不相同的 $C$ 颗来制作项链（顺序无关）。 项链的美丽度定义为所选宝石美丽度的按位异或（bitwise XOR）。

在所有制作项链的方式中，找出美丽度第 $K$ 大的项链的美丽度。（如果有多种方式的美丽度相同，全部计入。）

什么是按位异或（bitwise XOR）？

整数 $A$ 和 $B$ 的按位异或 $A \oplus B$ 定义如下：

将 $A \oplus B$ 写成二进制时，第 $2^k$ 位（$k \ge 0$）的数字在 $A$ 或 $B$ 中恰有一个在该位为 $1$ 时为 $1$，否则为 $0$。

例如，$3 \oplus 5 = 6$。（二进制下：$011 \oplus 101 = 110$。）

输入格式

输入按以下格式从标准输入给出：

N C K
D_1 V_1
⋮
D_N V_N

输出格式

打印答案。

样例

4 2 3
2 4
2 6
1 2
1 3

5

制作项链的方式有下面 4 种。

选择第 1 颗和第 3 颗宝石，项链的美丽度为 $4 \ {\rm XOR} \ 2 = 6$。

选择第 1 颗和第 4 颗宝石，项链的美丽度为 $4 \ {\rm XOR} \ 3 = 7$。

选择第 2 颗和第 3 颗宝石，项链的美丽度为 $6 \ {\rm XOR} \ 2 = 4$。

选择第 2 颗和第 4 颗宝石，项链的美丽度为 $6 \ {\rm XOR} \ 3 = 5$。

因此，美丽度第 3 大的项链的美丽度为 $5$。

3 1 2
1 0
1 0
1 0

0

制作项链的方式有 3 种，所有方式的美丽度都为 $0$。

10 3 11
1 414213562373095048
1 732050807568877293
2 236067977499789696
2 449489742783178098
2 645751311064590590
2 828427124746190097
3 162277660168379331
3 316624790355399849
3 464101615137754587
3 605551275463989293

766842905529259824

数据范围

• $1 \le C \le N \le 70$
• $1 \le D_i \le C$
• $0 \le V_i \lt 2^{60}$
• $1 \le K \le 10^{18}$
• 制作项链的方式至少有 $K$ 种。
• 输入中的所有值均为整数。