问题陈述

我们有 $N$ 颗宝石。第 $i$ 颗宝石的颜色和美丽度分别为 $D_i$ 和 $V_i$。
这里，每颗宝石的颜色是 $1, 2, \\ldots, C$ 中的一个，并且每种颜色至少有一颗宝石。

在 $N$ 颗宝石中，我们将选择 $C$ 颗带有不同颜色的宝石，用它们制作一个项链。（顺序无关紧要）项链的美丽度是所选宝石的按位异或操作结果。

在所有可能制作项链的方案中，找到以第 $K$ 大美丽度制作的项链的美丽度。（如果有多个方案具有相同的美丽度，我们计算所有方案。）

什么是按位异或操作？

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

• 当将 $A \\oplus B$ 表示为二进制时，$2^k$ 位（$k \\geq 0$）上的数字为 $1$ 当且仅当 $A$ 或 $B$ 在 $2^k$ 位上有 $1$，而另一个数字在该位上为 $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

有四种制作项链的方式，如下所示。

• 选择第一颗和第三颗宝石制作美丽度为 $4\\ {\\rm XOR}\\ 2 =6$ 的项链。
• 选择第一颗和第四颗宝石制作美丽度为 $4\\ {\\rm XOR}\\ 3 =7$ 的项链。
• 选择第二颗和第三颗宝石制作美丽度为 $6\\ {\\rm XOR}\\ 2 =4$ 的项链。
• 选择第二颗和第四颗宝石制作美丽度为 $6\\ {\\rm XOR}\\ 3 =5$ 的项链。

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

示例输入 2

3 1 2
1 0
1 0
1 0

示例输出 2

0

有三种制作项链的方式，所有方案的美丽度均为 $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